来自微信公众号：开点工作室（ID:kaidiancs）

排序是根据某种标准将一组记录重排的过程，是最常见的计算任务之一。关键字之间的比较次数和记录的移动次数决定着排序算法的时间复杂度。排序算法的时间复杂度又细分为最优时间复杂度、平均时间复杂度和最差时间复杂度。排序过程中除待排序记录所占空间外分配的工作空间为其空间复杂度。

根据排序记录的数量多少，排序又分为内部排序和外部排序。内部排序是指待排序的记录能够全部存储在计算机内存中并能完成排序的过程。记录数量过大，不能全部保存在内存中而需要借助于外存才能完成的排序是外部排序，简称为外排序。

基本的排序算法包括：

1.插入排序

插入排序（Insertion Sort）算法重复地将一个待排序的值插入到序列中已有序的子序列中，从而完成一组值的排序。每次将每个待排序的元素插入到有序子序列中的合适位置，直到序列中全部元素都有序时为止。

插入排序算法的过程是：对序列中最前面的两个元素进行比较，必要的话就进行交换。一趟排序完成。将序列中第三个值插入到前两个（已有序）值组成的子序列中的合适位置。这是第二趟排序。接下来将第4个值插入到序列中前三个值中的合适位置。每次插入时，已有序的子序列中元素个数增加一个。继续这个过程，直到表中所有的元素全部有序时为止。对含n个元素的数组进行插入排序，只需要n-1趟排序即可。每趟排序中，有序序列中的若干元素从后至前依次向后移动一个位置，为待排序元素腾出插入空间。

根据找到正确插入位置的机制，插入排序又分为直接插入排序及折半插入排序。

（1）直接插入排序

设待排序元素为A[i]，从A[i-1]开始向前进行顺序查找，找到满足下列条件的记录：A[j-1]≤A[i]≤A[j]。将元素A[i-1]至A[j]依次后移一个位置，元素A[i]插入到下标为j的位置。

这个过程中，从有序序列的末尾开始，反复把记录逐步后移一位，为待排序元素空出一个位置来存放待排序记录。

插入待排序元素时有两种特殊情况。一是A[i]≥A[i-1]，此时只进行了一次比较操作，而不需要移动任何元素。二是A[i]

插入排序中，仅在两元素交换时需要一个位置的临时空间，空间复杂度为O(1)。

插入排序有个特点，k趟排序后A[0],A[1],…,A[k]已有序，但它们均不一定位于其最终的有序位置上。它们的最终位置还要依赖于A[k+1],…,A[n-1]的排序结果。换句话说，在不进行最后一趟排序之前，所有元素都可能不在其最终的有序位置上。

如果数组初始时是逆序的，则出现插入排序的最坏情形。这种情况下，会导致最多次的比较和移动。相反的，如果数组初始时已经升序有序，则出现插入排序的最优情形。这种情形下，每趟扫描数组时都只进行比较而不发生交换操作。比较时能发现待排序元素已在有序表中的有序正确位置，所以，不需要移动任何元素。

（2）折半插入排序

在有序子序列中查找插入位置时，采用折半查找法替换顺序查找法，得到折半插入排序。就元素移动次数来说，折半插入排序与直接插入排序是一样的。当数据量较大时，折半查找的比较次数少于顺序查找的比较次数，所以折半插入排序的元素比较次数少于直接插入排序。

2.起泡排序

起泡排序（Bubble Sort）也称为冒泡排序，是一种简单的排序算法。它重复地扫描要排序的元素序列，一次比较相邻的两个元素，如果它们呈逆序则交换过来。

起泡排序算法的过程是：从A[0]开始，从前向后依次扫描A[0]到A[n-1]，若A[i]>A[i+1]，则交换A[i]与A[i+1]。当扫描到A[n-1]时一趟排序完成，此时序列中的最大元素已位于A[n-1]。接下来再从A[0]开始，依次扫描A[0]到A[n-2]，若A[i]>A[i+1]则交换它们。第二趟排序结束后序列中的第二大元素位于A[n-2]中。继续这个过程，直到比较A[0]与A[1]并完成必要的交换为止。

起泡排序也可以从后向前扫描，第一趟排序后将最小的元素交换到A[0]，第二趟排序后将次小的元素交换到A[1]，依此类推。

每趟起泡排序至少将一个元素移动到它的最终位置。

3.简单选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，利用的是“查找并交换”的思想。设元素保存在数组A[0],A[1],…,A[n-1]中，查找其中最小的元素，将它与第1个元素A[0]相交换，这称为一趟排序。然后查找子数组A[1],…,A[n-1]中的最小元素，并将它与数组第2个元素A[1]相交换。继续这个过程，直到仅剩最后两个元素A[n-2]和A[n-1]，这两元素中的较小者放到A[n-2]，较大者放在A[n-1]；排序完成。

采用顺序查找法查找A[i],…,A[n-1]中的最小元素时，得到简单选择排序。采用堆结构查找最小元素时，得到堆排序算法。

如果某个元素已位于其最终的有序位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个被移动到其最终位置上，因此对n个元素的序列进行排序总共进行至多n-1次交换。

4.希尔排序

希尔排序（Shell Sort）也称缩小增量排序法，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

初始排列序列基本有序时，插入排序可达到最优时间复杂度。同时，因为插入排序的代码简单，当待排序序列的长度n较小时，排序的总体开销较小。但插入排序过程中数据移动一位，效率较低。希尔排序将待排序序列分组，将相隔某增量值d整数倍的元素分在一组，并在组内采用插入排序使得各组内的元素有序。然后减小增量值d重新分组，组的个数减少而组内元素个数增多，再次采用插入排序使得各组内的元素有序。依此类推，直到增量值d=1时，全部元素均在同一组内，采用插入排序最终完成排序。

增量d较大时，分组的组数较多而组内元素个数较少，组内的插入排序可以达到较高效率。这些逆序对的调整提高了序列的有序性。当减小d后，组内元素个数增多但有序性增加。当d≠1时，组内相比较、交换的两个元素不相邻，数据移动的效率较高。

增量序列的选择要满足两个要求，一是序列为降序，且最后一个增量值必须为1；二是为避免重复比较，增量值之间不要成倍数关系。

5.快速排序

快速排序（Quick Sort）算法是采用分治法的一个非常典型的应用。

快速排序的过程是：先选择序列中的一个元素当作划分元素（称为枢轴），根据枢轴对序列进行划分，小于枢轴的所有元素放到枢轴的左侧，大于枢轴的所有元素放到它的右侧。最后再递归地对这两个子序列进行排序，从而完成对序列的排序。

一般地，选择序列的第一个元素作为枢轴。若含n个元素的序列元素随机分布，则枢轴将序列划分为元素个数大致相等的两个子序列，再继续划分为四个子序列，…，划分的次数不多于O(log2n)，每趟划分时最多对n个元素进行甄别，故时间复杂度为O(nlog2n)。但若序列已有序，每次选择的枢轴都是本序列中的最小值或是最大值，划分后的两个子序列中有一个为空，另外一个包含其余所有元素。此种情况下达到快速排序的最坏情形，时间复杂度为O(n2)。

6.堆排序

堆（Heap）是一棵完全二叉树，其中每个元素都大于等于它的所有孩子。二叉树根称为堆顶，它是堆中最大元素。这样的堆称为最大堆或大根堆。堆中任一棵子树也满足堆的定义。类似地，可以定义最小堆或小根堆，即每个元素都小于等于它的所有孩子。以下讨论以最大堆为例。

堆的逻辑结构是一棵完全二叉树，可以用数组保存。元素A[i]若有左子结点，则保存在A[2*i+1]中，若有右子结点，则保存在A[2*i+2]中。利用堆结构实现的排序过程称为堆排序（Heap Sort）。

对数组A[0],A[1],…,A[n-1]进行堆排序的第一步是采用递归思想建初始堆。将分别以A[(n-1)/2],A[(n-1)/2-1],…,A[0]为根的二叉树依次调整为子堆。

若当前调整以A[i]为根的子树，将A[i]与其两个子结点（若存在）中的较大者进行比较，若A[i]较大，则调整完成；若A[i]较小，则交换A[i]与其较大子结点，然后继续调整以A[i]为根的子树。直到A[i]大于它的所有子结点或是已经到达叶结点时为止。

当调整以A[i]为根的子树时，它的各子树已经满足堆的定义。若没有发生A[i]与其较大子结点之间的交换，表明以A[i]为根的子树已满足堆的定义；若发生交换，A[i]交换到其子结点的位置，这棵子树可能不再满足堆的定义，还需要继续调整。

当以A[0]为根的子树调整完毕，表明初始堆已经建成。这个过程的时间复杂度为O(n)。

初始堆建成后，将堆顶元素A[0]与堆中最后一个元素A[n-1]互换（实际上是将最大值输出到A[n-1]中保存）。调整以A[0]为根的子树为堆（注意，此时堆中元素个数为n-1），A[0],A[1],…,A[n-2]又成为最大堆。这称为一趟堆排序。再将堆顶元素A[0]与堆中最后一个元素A[n-2]互换，剩余元素重新整理为堆。继续这个过程。直到堆中只有一个元素A[0]时为止，堆排序完成。此时数组中保存的是已有序序列。

每次从堆中选择最大值时只需O(1)，调整堆的过程中，将新的堆顶放置到合适的位置，比较与交换的次数不超过二叉树的高。故时间复杂度为O(nlog2n)。

向堆中添加一个新元素的过程是，将元素添加为新的叶结点，同时保持树形是完全树。然后将该元素向根的方向移动：若新元素比父结点大，则交换两个结点，继续与新的父结点比较并进行必要的交换，直到其中的元素大小关系满足要求时为止。

7.二路归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。与快速排序算法一样，归并排序算法也采用了分治法的思想。

归并排序使用递归来实现：

如果数组中有多于1个元素

（1）将数组分为两半；

（2）归并排序左半段；

（3）归并排序右半段；

（4）将两个子数组归并为一个有序数组。

假定数组A[0],A[1],…,A[n-1]满足：A[0],…,A[m]升序排列，且A[m+1],…,A[n-1]也升序排序，归并操作可将两个有序子段合并为一个有序段。设i=0,j=m+1,k=1，比较A[i]与A[j]，不妨设较小者为A[i]，则B[k]=A[i],i++,k++。继续这个过程，直到两个有序序列中的一个为空，将另一个有序序列中的全部剩余元素拷贝到数组B中。归并完成。

归并排序过程中，为了保存每趟归并的结果，需要与原始待排序数组等大的临时数组。归并排序的空间复杂度为O(n)。

8.基数排序

若数组A[0],A[1],…,A[n-1]中均保存两位十进制整数。设置10个盒子，编号为0到9。现对数组中各元素按个位数分类，个位数为r(0≤r≤9)的元素依次放入编号为r的盒子中。这称为第一趟分配。之后按盒子编号从0到9，每个盒子中按数据放入的次序将数据收集起来。这称为第一趟收集。将收集的数据再按十位数分类，十位数为r(0≤r≤9)的元素依次放入编号为r的盒子中。这称为第二趟分配。之后是第二趟收集。结果为有序序列。

扩展上述排序思想，基数排序可以对任何数制的元素进行排序。若进制为r，则盒子数为r个。位数为k时，分配与收集的趟数为k。从权值低到权值高依次进行。

基数排序还可以应用到多关键字的排序中。

9.外部排序

如果一组记录数量太大而无法同时保存到主存中时，那么只能将其中一些记录先从磁盘中读出来进行排序，然后再把这些记录写回磁盘。这个过程不断重复下去，直到对整个文件进行了排序。这个过程中，每个记录可能被读出多次。

文件读取方式是顺序读取，采用归并的思想可以实现对文件中有序子序列的归并操作。若一个文件有n条记录，对这个文件进行外部排序需要log2n趟扫描，即对每条记录log2n次磁盘读写。

10.各种排序算法的比较