时间复杂度：$O(n)$.

基本思想：和快速排序的思想相似，也是对数组进行递归划分，但是有所差别的是，快速排序会递归处理划分的两边，而随机化的选择算法只选择一边。

时间复杂度:$O(3*floor(n/2))$

基本思想：成对地处理元素。先将一对输入元素相互比较，然后把较小的与当前最小值比较，较大的与当前最大值比较，因此每两个元素比较三次。

比较排序：通过元素间的比较对序列进行排序的算法称为比较排序。

常见的比较排序算法有：冒泡排序法、插入排序法、合并排序法、快速排序法，堆排序法等等。任何比较排序法在最坏情况下的时间复杂度为$O(nlogn)$。因此，合并排序和堆排序是渐进最优的。

​ 快速排序的最坏运行时间为$O(n^2)$，虽然这最坏情况的时间复杂度比较大，但快速排序通常是用于排序的最佳实用选择，这是因为其平均性能相当好，平均时间复杂度为$O(nlogn)$，并且$O(nlogn)$中的隐含常数因子很小。另外，它能够进行就地排序，因此在虚拟内存中也能较好的运行。

​ 堆排序像合并排序一样，时间复杂度为$O(nlogn)$;像插入排序一样，是一种原地排序（在任何时候只有常数个元素存储在数组外）。

分治法：将原问题划分为n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到了原问题的解。分治法在每一个递归上都有三个步骤：分解、解决、合并。而在本文中的合并排序法正是运用了这种分而治之的策略：把一个n个元素的数组先分成两个数组，然后继续分下去，知道分成n个数组；然后将其逐一合并排序，最终得到排列好了的数组。下面我们首先看一看合并排序了原理框图：（图中黑色部分看不见不要紧，只需了解是将数组L、R中浅颜色的元素从小到大依次填入数组A中）

对于秒/毫秒级计时，我们可以使用其自带库函数。在头文件time.h中，clock() 函数返回从 开启这个程序进程 到 程序中调用clock（）函数 时之间的CPU时钟计时单元数，返回单位是毫秒。另外，系统还定义了一个符号常量CLOCKS_PER_SEC。该常量等于每秒钟包括的系统时间单位数。因此，除以这个单位数，就可以得到秒数。time.h中将clock_t作为clock()作为clock()返回类型的别名。

对于微秒级计时，我们可以使用windows.h中的库函数QueryPerformanceCounter()。这个函数返回高精确度性能计数器的值,它可以以微妙为单位计时。由于该函数的精确计时的最小单位是与系统有关的，所以我们必须使用QueryPerformanceFrequency() 查询系统以得到QueryPerformanceCounter()返回的嘀哒声的频率，即返回每秒嘀哒声的个数。

插入排序法的时间复杂度为n的平方，对于较小的输入规模来说，插入排序法比合并排序法更快些。在最佳情况下，即输入数组已经排序好，则时间复杂度可表示为n,是一个线性函数；在最差情况下，即输入数组是逆序排列时，时间复杂度为 $an^2+bn+c$. 插入排序法的具体实现方法如下：

为成为国际语言，C++必须能处理需要16位的国际字符集Unicode,于是在传统的8位char型的基础上添加了wchar_t字符类型。在程序包含iostream文件时，将自动创建8个流对象：cin、cout、cerr、clog以及相对应的用于宽字符流的：wcin、wcout、wcerr、wclog。

在上篇文章《内存对齐》中说到了内存问题，今天我也遇到了可以用内存映射来解释的问题: 数组越界访问，出现死循环。