9. 第七章：排序
9.1 排序的基本知识
定义：排序就是将原本无序的序列重新排列成有序的序列。
9.1.1 排序的稳定性
如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
9.1.2 内部排序和外部排序
内部排序是数据记录在内存中进行排序。外部排序是因排序的数据很大，内存一次不能容纳全部的排序记录，在排序过程中需要访问外存。
9.2 插入类排序
9.2.1 直接插入排序
直接插入排序：首先以一个元素为有序的序列，然后将后面的元素依次插入到有序的序列中合适的位置直到所有元素都插入有序序列。
算法步骤
1）设待排序的记录存储在数组 
中，可以把第一个记录 
看作一个有序序列。
2）依次将 
插入已经排好序的序列 
中，并保持有序性。
时间复杂度为 
直接插入排序是稳定性是稳定的。
9.2.2 折半插入排序
折半插入排序将比较和移动这两个操作分离出来，也就是先利用折半查找找到插入的位置，然后一次性移动元素，再插入该元素。
折半插入排序的时间复杂度为 
稳定性：和直接插入排序稳定性相同，是稳定的。
9.2.3 希尔排序
希尔排序的基本思想：希尔排序本质上还是插入排序，只不过是把待排序序列分成几个子序列，再分别对这几个子序列进行直接插入排序。
算法步骤
1）设待排序的记录存储在数组 中，增量序列为 
。
2）第一趟取增量 
，所有间隔为 的记录分在一组，对每组记录进行直接插入排序。
3）第二趟取增量 
，所有间隔为 的记录分在一组，对每组记录进行直接插入排序。
4）依次进行下去，直到所取增量 
，所有记录在一组中进行直接插入排序。
①先以增量 
来分割序列，也就是下标为 
的关键字分成一组，下标为 
分成一组,然后对这些组分别进行直接插入排序，这就完成了一轮希尔排序。
②缩小增量（ 
，比如 
个数据序列，第一次增量 
,第二次增量 
,并且最后一个增量等于 
），所以第二轮以增量为 
进行类似的排序过程。
③接下来的第三轮，第四轮...都是类似的过程，直到最后一轮以增量为 。此时就是前面所说的直接插入排序。
- 时间复杂度：... 希尔排序的时间复杂度约为
在最坏情况下希尔排序的时间复杂度为 - 空间复杂度：希尔排序的空间复杂度为
- 稳定性：不稳定，由于不同的增量可能就会把相等的关键字划分到两个直接插入排序中进行排序， 可能就会造成相对顺序变化。
9.3 交换类排序
9.3.1 冒泡排序
算法步骤
1）设待排序的记录存储在数组 中，首先第一个记录和第二个记录关键字比较，若逆序则交换；然后第一个记录和第二个记录关键字比较……依次类推，直到第 
个记录和第 
个记录关键字比较完毕为止。第一趟排序结束，关键字最大的记录在最后一个位置。
2）第二趟排序，对前 个元素进行冒泡排序，关键字次大的记录在 位置。
3）重复上述过程，直到某一趟排序中没有进行交换记录为止，说明序列已经有序。
假设待排序表长为 ，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 
），则交换它们，直到序列比较完。我们称它为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，……，这样最多做 
趟冒泡就能把所有元素排好序。
- 空间复杂度：交换时开辟了存储空间来存储中间变量，所以空间复杂度为
- 时间复杂度
- 冒泡排序的时间复杂度和初始序列有关，可分为最好情况、最坏情况和平均情况。
- 在最好情况下，待排序序列本身是正序的（如待排序序列是非递减的，题目要求也是非递减排序），只需要一趟排序，n−1次比较，无交换记录。在最好情况下，冒泡排序时间复杂度为 。
- 在最坏情况下，待排序序列本身是逆序的（如待排序序列是非递增的，题目要求是非递减排序），需要n−1趟排序，每趟排序i−1次比较，总的比较次数为：
在最坏情况下，冒泡排序的时间复杂度为 。 - 在平均情况下，若待排序序列出现各种情况的概率均等，则可取最好情况和最坏情况的平均值。在平均情况下，冒泡排序的时间复杂度也为 。
- 稳定性：当两个关键字相等，if判断条件不成立，所以不会发生数据移动。所以是稳定的。
9.3.2 快速排序
快速排序算法是基于分治策略的，其算法思想如下。
1）分解：先从数列中取出一个元素作为基准元素。以基准元素为标准，将序列分解为两个子序列，使小于或等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。
2）治理：对两个子序列进行快速排序。
3）合并：将排好序的两个子序列合并在一起，得到原问题的解。
设当前待排序的序列为 
，其中 
，如果序列的规模足够小（只有一个元素），则完成排序，否则分3步处理，其处理过程如下。
1）分解：在 
中选定一个元素 
，以此为标准将要排序的序列划分为两个序列： 
和 
，并使序列 中所有元素小于等于 ，序列 中所有元素均大于 。此时基准元素已经位于正确的位置，它无须参加后面的排序，如图9-30所示。
2）治理：对于两个子序列 和 ，分别通过递归调用进行快速排序。
3）合并：由于对 和 的排序是原地进行的，所以在 和 都已经排好序后，合并步骤无须做什么，序列 就已经排好序了。
如何分解是一个难题，因为如果基准元素选取不当，有可能分解成规模为0和n−1的两个子序列，这样快速排序就退化为冒泡排序了。
例如，序列（30, 24, 5, 58, 18, 36, 12, 42, 39），第一次选取5作为基准元素，分解后，如图9-31所示。
第二次选取12作为基准元素，分解后如图9-32所示
是不是有点像冒泡了？这样做的效率是最差的，最理想的状态是把序列分解为两个规模相当的子序列，那么怎么选择基准元素呢？一般来说，基准元素选取有以下几种方法。
- 取第一个元素。
- 取最后一个元素。
- 取中间位置元素。
- 取第一个、最后一个、中间位置元素三者之中位数。
- 取第一个和最后一个之间位置的随机数k（low k high），选R[k]做基准元素。
目前并没有明确的方法说哪一种基准元素选取方案最好，在此以选取第一个元素做基准为例，说明快速排序的执行过程。
算法步骤
1）首先取数组的第一个元素作为基准元素 
。
2）从右向左扫描，找小于等于 
的数，如果找到，则 
和 
交换， 
。
3）从左向右扫描，找大于 的数，如果找到，则 和 交换， 
。
4）重复第2步和第3步，直到 
和 
重合，返回该位置 
，该位置的数正好是 元素。
5）至此完成一趟排序。此时以 
为界，将原序列分为两个子序列，左侧子序列元素小于等于 ，右侧子序列元素大于 ，再分别对这两个子序列进行快速排序。
快速排序是一种基于分治法的排序方法。每一趟快排选择序列中任一个元素作为枢轴(pivot)(通常选第一个元素)，将序列中比枢轴小的元素都移到枢轴前边，比枢轴大的元素都移到枢轴后边。
1.划分函数
2.快速排序递归算法
- 时间复杂度：最好情况下时间复杂度为
,待排序序列越无序，算法效率越高。 最坏情况下时间复杂度为 ，待排序序列越有序，算法效率越低。 - 空间复杂度：由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为
(每次partition都很均匀)递归树的深度 
最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)； - 稳定性：快速排序是不稳定的，是因为存在交换关键字。
9.4 选择类排序
简单选择排序
- 空间复杂度：需要额外的存储空间仅为交换元素时借助的中间变量，所以空间复杂度是O(1)
- 时间复杂度：关键操作在于交换元素操作，整个算法由双重循环组成，外层循环从0到n-2一共n-2+1=n-1次，对于第i层外层循环，内层循环执行n-1-(i+1)+1=n-i-1次。当i=0,内层循环执行n-1次，当i=n-2,内层循环执行1次，所以是一个等差数列求和,一共为(1+n-1)(n-1)/2=n(n-1)/2 ,所以时间复杂度为O(n^2)
- 稳定性：不稳定 原因就在于交换部分会打破相对顺序
堆排序
什么是堆？
- 堆是一棵完全二叉树，而且满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。
- 如果是每个结点的值都不小于它的左右孩子结点的值，则称为大顶堆。
- 如果是每个结点的值都不大于它的左右孩子结点的值，则称为小顶堆。
什么是堆排序？
我们知道对于一个堆来说，它的根结点是整个堆中所有结点的值的最大值(大顶堆)或者最小值(小顶堆)。所以堆排序的思想就是每次将无序序列调节成一个堆，然后从堆中选择堆顶元素的值，这个值加入有序序列，无序序列减少一个，再反复调节无序序列，直到所有关键字都加入到有序序列。
时间复杂度：堆排序的总时间可以分为①建堆部分+②n-1次向下调整堆 堆排序的时间复杂度为O(n)+O(nlog2n)=O(nlog2n)
堆排序不稳定
9.5 归并排序
假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并，得到 ⌈n/2⌉个长度为2或1的有序表；再两两归并，……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。
例如：49 38 65 97 76 13 27
- ①首先将整个序列的每个关键字看成一个单独的有序的子序列
- ②两两归并，49和38归并成{38 49} ，65和97归并成{65 97}，76和13归并成{13 76}，27没有归并对象
- ③两两归并，{38 49}和{65 97}归并成{38 49 65 97}，{13,76}和27归并成{13 27 76}
- ④两两归并，{38 49 65 97}和{13 27 76}归并成{13 27 38 49 65 76 97}
时间复杂度：O(nlog2n)
空间复杂度:因为需要将这个待排序序列转存到一个数组，所以需要额外开辟大小为n的存储空间，即空间复杂度为O(n)
稳定性：稳定
9.6 基数排序
基数排序(也叫桶排序)是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。
例子：53, 3, 542, 748, 14, 214, 154, 63, 616
- 补充位数：053, 003, 542, 748, 014, 214, 154, 063, 616
- 桶实际是一个队列，先进先出(从桶的上面进，下面出)
- 关键字数量为n,关键字的位数为d,比如748 d=3，r为关键字的基的个数，就是组成关键字的数据的种类，比如十进制数字一共有0至9一共10个数字，即r=10
空间复杂度：需要开辟关键字基的个数个队列，所以空间复杂度为O(r)
时间复杂度：需要进行关键字位数d次"分配"和"收集"，一次"分配"需要将n个关键字放进各个队列中，一次"收集"需要将r个桶都收集一遍。所以一次"分配"和一次"收集"时间复杂度为O(n+r)。d次就需要O(d(n+r))的时间复杂度。
稳定性：由于是队列，先进先出的性质，所以在分配的时候是按照先后顺序分配，也就是稳定的，所以收集的时候也是保持稳定的。即基数排序是稳定的排序算法。
外部排序
需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序的方法就叫做外部排序。
如何得到初始的归并段
- 置换选择排序：解决排序段放入内存的问题
如何减少多个归并段的归并次数
- 最佳归并树：最少的归并次数（I/O次数）
如何每次m路归并快速得到最小的关键字
- 败者树：减少比较次数
