第7章 排序

第7章 排序

任何通用的排序算法均需要NlogN次比较

7.1 预备知识

略

7.2 插入排序

插入排序思想：在已排序状态插入新元素

插入排序的最坏情形和平均情形均为n的平方

7.3  一些简单排序算法的下界

通过比较和交换来进行排序的算法本质上是消除序列中的逆序数，因此求解该算法的时间复杂度时，需要计算其排序序列的逆序数。

7.4 希尔排序

希尔排序需要一个最低为1的增量序列。

希尔排序的本质则是通过比较非相邻元素来消除逆序数的高级插入排序版。

相对于只比较相邻元素的插入排序，希尔排序比较了非相邻元素，保证消除了至少为1的逆序数，因此其性能有可能突破插入排序的n平方界。

希尔排序的增量序列最小为1，保证了序列每个都可被比较排序到，保证序列最终有序。

希尔排序过程中，通过不断缩减增量序列，跳跃比较不同的元素。

一个k排序过的序列保持其k排序性。

k排序的一般思路：对于k，k+1，。。。n-1的每一个元素i，将其放到i，i-k，i-2k。。的合适位置上。

其实就是对k个子数组执行插入排序。

希尔建议的序列为开始序列为n/2的下限，后续序列为前面序列的一半，直至1。

使用希尔增量的最坏情形运行时间为n平方。

7.5 堆排序

堆排序利用了每次删除操作后空出的位置，将删除后的元素放到空出的位置节省内存。

7.6 归并排序

归并排序使用了所有流行排序中最少的比较次数。

归并排序是分治算法思想的运用。

其本质是递归对两个已排序子序列进行排序。

7.7 快速排序

快速排序一般采用三数中值分割法。

快速排序的本质是递归地将元素放在合适的位置。也正因为这样，提供了筛选出第k大元素的nlogn算法。

快速元素一般对于遇到相等元素时采用停止的算法。

对于小数组，快速排序不如插入排序，所以当n小于20时，可进行插入排序。

快速排序一定考虑相等序列的情形，因为递归会将相等的元素放到一起。

7.8 排序算法的一般下界

略

7.9 选择问题的决策树下界

如果决策树所有的叶子都有深度d或更深，则决策树必须至少有2d个叶子。

对任何基于比较的算法，找最小元都必须至少使用N-1次比较。

从N个元素中找最小元的决策是必须至少有2的n-1次方个叶子。

7.10 对手下界

7.11 线性时间的排序：桶排序和基数排序

桶排序使用了额外的数组，利用空间换时间。通过使用数组的位置可以快速索引的特性，将需要排序的数组值与数值位置映射起来。

基数排序用于对数字范围较大的数字的排序，通过依次对不同的位上的数排序，来达到对数的整体排序。

计数基数排序的方便之处在于解决基数排序时表的创建，通过引入一个额外数组用于记录需排序值的位置，达到将值放到数组正确位置的做法。

7.12 外部排序

外部排序一般利用了归并算法，通过将外存中的记录读到内存排序并写回外存，接着依次读取已经排序好的外存中的记录进行边读取边归并操作。

多路合并改善了两路合并的多次io的性能，可以通过使用优先队列，对多路的记录进行归并排序。

多相合并则是在极大节约磁盘空间的情况下的合并算法。

替换选择在与最优化的利用内存，尽量通过一次内存排序的记录数的提高减少归并的次数。

疑难点