数据结构基础温故-7.排序
排序（Sorting）是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序，特别是高效率地进行排序时计算机工作者学习和研究的重要课题之一。排序有内部排序和外部排序之分，若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序，反之则为外部排序。本篇主要介绍插入排序、交换排序、选择排序和归并排序这几种内部排序方法。
首先，我们今天的目标就是编写一个SortingHelper类，它是一个提供了多种排序方法的帮助类，后面我们的目标就是实现其中的各种排序静态方法：
public static class SortingHelper<T> where T : IComparable { public static void StraightInsertSort(T[] arr) { } public static void ShellSort(T[] arr) { } public static void BubbleSort(T[] arr) { } public static void QuickSort(T[] arr) { } public static void SimpleSelectSort(T[] arr) { } public static void HeapSort(T[] arr) { } public static void MergeSort(T[] arr) { } }
一、插入类排序
插入排序（Insertion Sort）的主要思想是不断地将待排序的元素插入到有序序列中，是有序序列不断地扩大，直至所有元素都被插入到有序序列中。例如我们平常玩扑克牌时的抓牌操作就是一个插入操作的例子，每抓一张牌后我们便将其插入到合适的位置，直到抓完牌位置，这时我们手上的牌就成了一个有序序列。
1.1 直接插入排序
直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
public static void StraightInsertSort(T[] arr) { int i, j; T temp; for (i = 1; i < arr.Length; i++) { j = i - 1; temp = arr[i]; while (j >= 0 && temp.CompareTo(arr[j]) < 0) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } }
通过初始化10000个随机数的数组传入进行测试，借助CodeTimer类进行性能计数的结果如下图所示：
排序后的数组结果如下图所示，后面的排序结果就不再一一展示了：
以上代码中，while循环条件中j>=0用于避免向前查找合适位置而导致j值超出数组界限，这使得每次while循环都要进行两次比较，可以通过设置监哨来对该算法进行改进，以减少循环中的比较次数。所谓监哨就是利用数组的某个元素来存放当前待排序记录，从而达到避免数组越界和减少比较次数的目的。这里使用arr[0]来作为监哨，改进后的代码如下：
public static void StraightInsertSortWithSentry (T[] arr) { int i, j; for (i = 1; i < arr.Length; i++) { j = i - 1; arr[0] = arr[i]; // 将插入元素存放于监哨arr[0]中 while (arr[0].CompareTo(arr[j]) < 0) { arr[j + 1] = arr[j]; // 移动记录 j--; } arr[j + 1] = arr[0]; // 将插入元素插入到合适的位置 } }
使用监哨的前提是arr[0]元素必须不在待排序序列中，否则在排序前需要在arr[0]处插入一个额外元素，这样会使数组中所有元素向右移动一位。
总结：直接插入排序最好情况时间复杂度为O(n)，最坏情况下（逆序表）时间复杂度为O(n2)，因此它只适合于数据量较少的情况使用。
1.2 希尔排序
希尔排序是D.L.Shell于1959年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是O(n*n)的，希尔排序算法是突破这个时间复杂度的第一批算法之一，它是直接插入排序的升级版。希尔排序的基本思想是：将待排序的记录分成几组，从而减少参与直接插入排序的数据量，当经过几次分组之后，记录的排列已经基本有序，这时再对所有记录实施直接插入排序。
希尔排序的主要特点是排序的每一趟均以不同的间隔数对子序列进行排序，当间隔数很大时，被移动的元素是以跳跃式进行的。而当间隔数=1时，序列则几乎已经有序，只需要进行很少的元素移动，就能最终达到排序的目的。
public static void ShellSort(T[] arr) { int i, j, d; T temp; for (d = arr.Length / 2; d >= 1; d = d / 2) { for (i = d; i < arr.Length; i++) { j = i - d; temp = arr[i]; while (j >= 0 && temp.CompareTo(arr[j]) < 0) { arr[j + d] = arr[j]; j = j - d; } arr[j + d] = temp; } } }
在10000个随机数的数组中测试的性能结果如下图所示：
总结：Shell排序适用于待排序记录数量较大的情况，在此情况下，Shell排序一般要比直接插入排序要快（从直接插入排序结果的1061ms到希尔排序的21ms）。1971年，斯坦福大学的两位教授在大量实验的基础上推导出Shell排序的时间复杂度约为O(n1.3)，使得我们终于突破了慢速排序的时代（超越了时间复杂度为O(n2)）。
二、交换类排序
交换排序（Exchange Sort）的主要思路就是在排序过程中，通过对待排序记录序列中的元素进行比较，如果发现次序相反，就将存储位置交换来达到排序目的。
2.1 冒泡排序
冒泡排序（Bubble Sort）是一种简单的交换排序方法，其基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
public static void BubbleSort(T[] arr) { int i, j; T temp; for (j = 1; j < arr.Length; j++) { for (i = 0; i < arr.Length - j; i++) { if (arr[i].CompareTo(arr[i + 1]) > 0) { // 核心操作：交换两个元素 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } }
在10000个随机数的数组中测试的性能结果如下图所示：
从上图可以看出，冒泡排序对于无序待排序数组的耗时接近了3秒钟，垃圾回收次数更是达到了1143次左右。另外，上面的代码对于接近有序的待排序数组的处理效率不高，需要避免因已经有序的情况下的无意义循环判断，因此可以进行如下的改进：
public static void BubbleSort(T[] arr) { int i, j; T temp; bool isExchanged = true; for (j = 1; j < arr.Length && isExchanged; j++) { isExchanged = false; for (i = 0; i < arr.Length - j; i++) { if (arr[i].CompareTo(arr[i + 1]) > 0) { // 核心操作：交换两个元素 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; // 附加操作：改变标志 isExchanged = true; } } } }
总结：冒泡排序在运行时间方面，待排序的记录越接近有序，算法的执行效率就越高，反之，执行效率则越低，它的平均时间复杂度为O(n2)。
2.2 快速排序
冒泡排序在扫描过程中只对相邻的两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序。如果通过两个不相邻元素的交换能够消除待排序记录中的多个逆序，则会大大加快排序的速度。快速排序（Quick Sort）正是通过不相邻元素交换而消除多个逆序的，因而可以认为其是冒泡排序的升级版。
快速排序是由C.A.R Hoare提出并命名的一种排序方法，在目前各种排序方法中，这种方法对元素进行比较的次数较少，因而速度也比较快，被认为是目前最好的排序方法之一。在.NET中的多个集合类所提供的Sort()方法中都使用了快速排序对集合中的元素进行排序。
快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
快速排序的核心步骤为：
①获取中轴元素
②i从左至右扫描，如果小于基准元素，则i自增，否则记下a[i]
③j从右至左扫描，如果大于基准元素，则i自减，否则记下a[j]
④交换a[i]和a[j]
⑤重复这一步骤直至i和j交错，然后和基准元素比较，然后交换。
（1）主入口：获取索引并对左右两个区间进行递归操作
public static void QuickSort(T[] arr, int low, int high) { if (low < high) { int index = Partition(arr, low, high); // 对左区间递归排序 QuickSort(arr, low, index - 1); // 对右区间递归排序 QuickSort(arr, index + 1, high); } }
（2）核心：获取基准值的实际存储位置
private static int Partition(T[] arr, int low, int high) { int i = low, j = high; T temp = arr[i]; // 确定第一个元素作为"基准值" while (i < j) { // Stage1:从右向左扫描直到找到比基准值小的元素 while (i < j && arr[j].CompareTo(temp) >= 0) { j--; } // 将比基准值小的元素移动到基准值的左端 arr[i] = arr[j]; // Stage2:从左向右扫描直到找到比基准值大的元素 while (i<j && arr[i].CompareTo(temp) <= 0) { i++; } // 将比基准值大的元素移动到基准值的右端 arr[j] = arr[i]; } // 记录归位 arr[i] = temp; return i; }
在10000个随机数的数组中测试的性能结果如下图所示：
从上图可以看出，快速排序对于无序待排序数组的耗时只有15ms，比Shell排序还快了6ms，它的确是“快速”的。
总结：快速排序的平均时间复杂度为O(nlog2n)，在平均时间下，快速排序时目前被认为最好的内部排序方法。但是，如果待排序记录的初始状态有序，则快速排序则会退化为冒泡排序，其时间复杂度为O(n2)。换句话说，待排序记录越无序，基准两侧记录数量越接近，排序速度越快；相反，待排序记录越有序，则排序速度越慢。
对于快速排序的改进一般集中在以下几个方面：
①当划分到较小的子序列时，通常可以使用插入排序替代快速排序；
②使用三平均分区法代替第一个元素作为基准值所出现的某些分区严重不均的极端情况；
③使用并行化处理排序；
三、选择类排序
选择排序（Selection Sort）是以选择为基础的一种常用排序方法，其基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的记录序列的最后，直到全部排列完为止。
3.1 简单选择排序
简单选择排序的基本思想是：第一趟从所有的n个记录中选择最小的记录放在第一位，第二趟从n-1个记录中选择最小的记录放到第二位。以此类推，经过n-1趟排序之后，整个待排序序列就成为有序序列了。
public static void SimpleSelectSort(T[] arr) { int i, j, k; T temp; for (i = 0; i < arr.Length - 1; i++) { k = i; // k用于记录每一趟排序中最小元素的索引号 for (j = i + 1; j < arr.Length; j++) { if (arr[j].CompareTo(arr[k]) < 0) { k = j; } } if(k != i) { // 交换arr[k]和arr[i] temp = arr[k]; arr[k] = arr[i]; arr[i] = temp; } } }
在10000个随机数的数组中测试的性能结果如下图所示：
总结：简单选择排序外循环n-1趟，内循环执行n-i趟，因此，简单选择排序的平均时间复杂度为O(n2)，和直接插入排序、冒泡排序一样均超过了1秒钟。
3.2 堆排序
堆排序（Heap Sort）是由J.Williams在1964年提出的，它是在选择排序的基础上发展起来的，比选择排序的效率要高，因此也可以说堆排序是选择排序的升级版。堆排序除了是一种排序方法外，还涉及到方法之外的一些概念：堆和完全二叉树。这里主要说说什么是堆？
如果将堆看成一棵完全二叉树，则这棵完全二叉树中的每个非叶子节点的值均不大于（或不小于）其左、右孩子节点的值。由此可知，若一棵完全二叉树是堆，则根节点一定是这棵树的所有节点的最小元素或最大元素。非叶子节点的值大于其左、右孩子节点的值的堆称为大根堆，反之则称为下小根堆，如下图所示。
如果按照层序遍历的方式给结点从1开始编号，则结点之间满足如下关系：
（1）基本思想
堆排序的基本思想是：首先将待排序的记录序列构造为一个堆，此时选择堆中所有记录的最小记录或最大记录，然后将它从堆中移出，并将剩余的记录再调整成堆，这样就又找到了次大（或次小）的记录。以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。
（2）处理步骤
堆排序的处理步骤如下：
①设堆中元素个数为n，先取i=n/2-1，将以i节点为根的子树调整成堆，然后令i=i-1。再将以i节点为根的子树调整成堆，如此反复，直到i=0为止，即完成初始堆的创建过程；
②首先输出堆顶元素，将堆中最后一个元素上移到原堆顶位置，这样可能会破坏原有堆的特性，这时需要重复步骤①的操作来恢复堆；
③重复执行步骤②，直到输出全部元素为止。按输出元素的前后次序排列起来，就是一个有序序列，从而也就完成了对排序操作。
假设待排序序列为（3,6,5,9,7,1,8,2,4），那么根据此序列创建大根堆的过程如下：
①将（3,6,5,9,7,1,8,2,4）按照二叉树的顺序存储结构转换为如下图所示的完全二叉树；
②首先，因为n=9，所以i=n/2-1=3，即调整以节点9为根的子树，由于节点9均大于它的孩子节点2和4，所以不需要交换；最后，i=i-1=2。
③当i=2时，即调整以节点5为根的子树，由于节点5小于它的右孩子8，所以5需要与8交换；最后，i=i-1=1。
④当i=1时，即调整以节点6为根的子树，由于节点6均小于它的左、右孩子9和7，故节点6需要与较大的左孩子9交换；最后i=i-1=0。
⑤当i=0时，即调整以3为根的子树，由于节点3均小于它的左、右孩子9和8，故节点3需要与较大的左孩子9交换；交换之后又因为节点3小于它的左、右孩子节点6和7，于是需要与较大的右孩子7交换。
⑥如上图所示，至此就完成了初始堆的创建，待排序序列变为（9,7,8,6,3,1,5,2,4）。
（3）代码实现
①主入口：首先递归创建初始堆，其次递归调整大根堆；
public static void HeapSort(T[] arr) { int n = arr.Length; // 获取序列的长度 // 构造初始堆 for (int i = n / 2 - 1; i >= 0; i--) { Sift(arr, i, n - 1); } // 进行堆排序 T temp; for (int i = n - 1; i >= 1; i--) { temp = arr[0]; // 获取堆顶元素 arr[0] = arr[i]; // 将堆中最后一个元素移动到堆顶 arr[i] = temp; // 最大元素归位,下一次不会再参与计算 Sift(arr, 0, i - 1); // 重新递归调整堆 } }
②核心：创建堆的过程；
private static void Sift(T[] arr, int low, int high) { // i为欲调整子树的根节点索引号，j为这个节点的左孩子 int i = low, j = 2 * i + 1; // temp记录根节点的值 T temp = arr[i]; while (j <= high) { // 如果左孩子小于右孩子，则将要交换的孩子节点指向右孩子 if (j < high && arr[j].CompareTo(arr[j + 1]) < 0) { j++; } // 如果根节点小于它的孩子节点 if (temp.CompareTo(arr[j]) < 0) { arr[i] = arr[j]; // 交换根节点与其孩子节点 i = j; // 以交换后的孩子节点作为根节点继续调整其子树 j = 2 * i + 1; // j指向交换后的孩子节点的左孩子 } else { // 调整完毕，可以直接退出 break; } } // 使最初被调整的节点存入正确的位置 arr[i] = temp; }
在10000个随机数的数组中测试的性能结果如下图所示：
从上图可以看出，快速排序对于无序待排序数组的耗时只有19ms，比Shell排序还快了2ms，仅仅比快速排序慢了4ms，可以说跟快速排序一样快。
总结：堆排序的执行时间主要由建立初始堆和反复调整堆这两个部分的时间开销组成，由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlog2n)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。另外，由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。
四、归并类排序
归并排序（Merging Sort）是利用“归并”技术进行的排序，所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。其基本思想是：将这些有序的子序列进行合并，从而得到有序的序列。
4.1 二路归并排序介绍
利用两个有序序列的合并实现归并排序就称为二路归并排序，其基本思想是：如果初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到（表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止。
例如一个本是无序的数组序列{16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14}，通过两两合并排序后再合并，最终获得了一个有序的数组，如下图所示：
观察上图，细心的你会惊讶，它十分像一棵倒置的完全二叉树，通常涉及到完全二叉树结构的排序算法，效率一般都不会低。
4.2 二路归并排序实现
（1）主入口：首先归并左边子序列，其次归并右边子序列，最后归并当前序列
public static void MergeSort(T[] arr, int low, int high) { if (low < high) { int mid = (low + high) / 2; MergeSort(arr, low, mid); // 归并左边的子序列（递归） MergeSort(arr, mid + 1, high); // 归并右边的子序列（递归） Merge(arr, low, mid, high); // 归并当前前序列 } }
（2）核心：将两个有序的子序列合并成一个有序序列
private static void Merge(T[] arr, int low, int mid, int high) { // result为临时空间，用于存放合并后的序列 T[] result = new T[high - low + 1]; int i = low, j = mid + 1, k = 0; // 合并两个子序列 while (i <= mid && j <= high) { if (arr[i].CompareTo(arr[j]) < 0) { result[k++] = arr[i++]; } else { result[k++] = arr[j++]; } } // 将左边子序列的剩余部分复制到合并后的序列 while (i <= mid) { result[k++] = arr[i++]; } // 将右边子序列的剩余部分复制到合并后的序列 while (j <= high) { result[k++] = arr[j++]; } // 将合并后的序列覆盖合并前的序列 for (k = 0, i = low; i <= high; k++, i++) { arr[i] = result[k]; } }
在10000个随机数的数组中测试的性能结果如下图所示：
从上图可以看出，快速排序对于无序待排序数组的耗时也只有19ms，跟快速排序、堆排序属于一个级别。
总结：二路归并排序易于在链表上实现，它的时间复杂度在最好、最坏情况下均为O(nlog2n)，但二路归并排序与其他排序相比，需要更多的临时空间。从Merge方法可以看出，需要频繁地创建临时空间来存储合并后的数据，可以让所有的Merge方法共用同一块临时空间，以最大限度地减少内存使用。
五、小结
本篇复习了多种排序方法，但其中并无绝对好与不好的算法，每一种排序方法都有其优缺点，适合于不同的环境。因此，在实际应用中，应根据具体情况作出选择。
（1）当待排序序列的记录数n较小的时候（一般n<=50），可以采用直接插入排序、直接选择排序或冒泡排序：
若序列初始状态基本为正序，则应选用直接插入排序、冒泡排序。
如果单条记录本身信息量较大，由于直接插入排序所需的记录移动操作较直接选择排序多，因此用直接选择排序较好。
（2）当待排序序列的记录数n较大的时候，则应采用时间复杂度为O(nlog2n)的排序方法，如：快速排序、堆排序或归并排序。
快速排序时目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短，.NET中集合类的内置排序方法（例如：Array.Sort()）也是使用了快速排序实现的。
堆排序需要的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况O(n2)。
归并排序需要大量的辅助空间，因此不值得提倡使用，但是如果要将两个有序序列组合成一个新的有序序列，最好的方法就是归并排序。
参考资料
（1）陈广，《数据结构（C#语言描述）》
（2）程杰，《大话数据结构》
（3）段恩泽，《数据结构（C#语言版）》
（4）yangecnu，《浅谈算法和数据结构：基本排序算法》、《浅谈算法和数据结构：合并排序》、《浅谈算法和数据结构：快速排序》
