Chapter 8. 排序

公式与性质

• 各种排序算法的性质

  算法种类	时间复杂度	空间复杂度	稳定性
  直接插入排序	O(n^2)	O(1)	稳定
  冒泡排序	O(n^2)	O(1)	稳定
  简单选择排序	O(n^2)	O(1)	不稳定
  希尔排序	n范围适当时为 O(n^{1.3}) ，最坏 O(n^2)	O(1)	不稳定
  快速排序	O(n \log _2 n) ，极端情况 O(n^2)	O(\log _2 n)	不稳定
  堆排序	O(n \log _2 n)	O(1)	不稳定
  二路归并排序	O(n \log _2 n)	O(n)	稳定
  基数排序	O(d(n+r))	O(r)	稳定

  • n 个初始归并段进行 m 路归并，完美归并需要满足 (n-1)\%(m-1)=0 ，否则可以补充 k 个虚段使 (n+k-1)\%(m-1)=0 。

概念

• 直接插入排序可能出现"在最后一趟开始之前，所有元素都不在最终位置上"。

  最后一个元素可能插入到第一个位置。

• 快速排序在待排序待数据已基本有序的情况下不利于发挥其长处。

  会导致基准元素的左右两边划分不均匀，决策树不平衡。在极端情况下，决策树仅有左/右子树，此时排序趟数（ = 树高）由（类平衡）二叉树 O(\log _2 n) 退化为链表 O(n) 。

• 简单选择排序每趟都能确定一个元素的最终位置。

• 外部排序总时间 = 外存读/写时间 + 内部归并时间 + 内部排序总时间。

考点

• 直接插入排序的第一趟排序从第二个元素开始。

• 希尔排序的组内排序采用的是直接插入排序。

• 冒泡排序将元素排成有序后，需要再排一次才能确定元素已经有序。

• 快速排序以第一个元素为基准时，先从后往前比较，交换后再从前往后比较，依次类推。

• 冒泡排序和选择排序每次至少确定一个值的位置。

• 归并排序的特征是局部有序。

• 快速排序若基准元素选择的是最大/最小元素，则第 n 趟排序能确定 n 个位置；若选择的是中间元素，则能确定 n+1 个位置。

• 快速排序为减少算法的递归深度，可以在每次分区后，先处理较短的部分。

  设第一次调用 quick_sort() 的调用栈深度为 1 ，则深度为 n 时再调用 quick_sort() 的调用栈为 n+1 。先处理短的部分，长的部分就会作为一个整体保存，只占用一层栈。

• 快速排序在数列有序时最慢，在每次划分都能等分时最快。

• 快速排序的递归深度最大为 n （退化为链表），最小为 \log _2 n （平衡二叉树），

• 对 7 个元素进行快速排序，在最好情况下的关键字比较次数是 10 。

  最好情况即每次都能平分：

                   6 ----> 依次和其他6个数比较      1 * 6 = 6 次
                  / \
  和1,4比较 <---- 3   8 ----> 和7,9比较            2 * 2 = 4 次
                / \ / \
               1  4 7  9
  

• 对 15 个元素进行快速排序，则元素的比较次数至少是 34 。

  1） 7-1-7， 14 次
  2） 3-1-3，3-1-3， 6*2=12 次
  3） 1-1-1，1-1-1，1-1-1，1-1-1， 2*4=8 次
  共 14+12+8=34 次

• 堆排序建堆 \ne 依次插入空堆；建堆是指从 \lceil \frac n 2 \rceil 号结点开始依次开始调整（比较该结点和其左右子结点）。

• 二路归并排序中 Merge 函数（将两个有序表归并为一个有序表）的时间复杂度为 O(n) ，将数列不断分为子数列的时间复杂度为 O(log _2 n) （并行树），故总的时间复杂度为 O(n \log _2 n) 。

• 归并排序的内部排序是相当于两个有序链表合并的比较。

• 快速排序、堆排序、归并排序可以并行执行；基数排序、冒泡排序不能并行执行。

• 从 k 路归并构建的败者树中选取一个关键字最小的记录，所需时间为 O(\log _k n) 。

  取决于败者树深度。

• 二路归并败者树是一颗完全二叉树。

• 大根/小根堆的堆更新可以从根到分支或叶子结点；更新败者树必须从叶子结点到根结点结束。

• m 路归并排序的败者树，内部归并的次数与 m 无关。

• n 个记录做 m 路平衡归并排序，内存工作区能容纳 k 个记录，则需要 \left \lceil \log _m \lceil \frac n k \rceil \right \rceil 趟归并排序。

• 在做 m 路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置 2m 个输入缓冲区和 2 个输出缓冲区。

  输入与内部归并的并行：m 路归并中时，从磁盘向另外 m 个缓冲区写数据，总共 2m 个缓冲区；
  内部归并与输出的并行：输出缓冲区满时才能输出，输出时内部归并的结果写入另一个缓冲期即可，总共 2个缓冲区。

• 置换-选择排序产生的有序段个数 m 与待排文件、内存工作区大小、记录个数 n 都有关。

• 9 个初始归并段构建的 3 阶最佳归并树中度为 3 度结点个数为 4 。

  k 阶最佳归并树只有度为 0 和 k 的结点。9 个初始归并段表示度为 0 的结点个数为 9 ，度数+1=结点数 ，故 3*n_3+1=9+n_3, n_3=4 。