第 12 讲 · 排序算法 | L.D.J 的私家工坊

排序把无序关键字序列变成有序序列。评价排序不能只看大 $O$ ：还要看比较和移动次数、额外空间、原始次序的影响，以及稳定性。

若两个元素关键字相等，排序后仍保持原先相对次序，称稳定排序。稳定性在同一记录按多个字段依次排序时很重要。

直接插入排序

第 $i$ 趟开始前，前 $i$ 个元素已经有序；取下一个元素，在有序前缀中找到位置，把更大元素右移后插入。

折半查找可以减少确定插入位置的比较次数，但元素移动仍为 $O(n^2)$ 。

第 $i$ 趟从未排序后缀中选最小元素，与第一个未排序位置交换。每趟结束后，有序前缀增加一个最终元素。

比较次数与输入次序无关，始终是 $n(n-1)/2$ ；交换次数较少。普通交换可能越过相等元素，因此不稳定，时间 $O(n^2)$ 。

一趟从前向后比较相邻逆序对并交换，最大元素逐渐“冒”到未排序区末尾。若某趟没有交换，说明已经有序，可以提前结束。

最好 $O(n)$ ，最坏 $O(n^2)$ ；只交换严格逆序的相邻元素时稳定。

按间隔 gap 把序列分组，对每组做插入排序；逐步缩小间隔，最后以 gap=1 完成整体插入排序。较大的间隔让元素提前跨越长距离。

复杂度依赖增量序列，课程中不要求用一个简单公式概括；它是原地排序，但相等元素可能跨组移动，因此通常不稳定。

堆排序将根与末结点交换后对剩余堆向下调整

先建大顶堆，堆顶是当前最大元素；把堆顶与末元素交换，缩小堆范围，再向下调整恢复堆序。

建堆 $O(n)$ ，随后 $n-1$ 次调整各 $O(\log n)$ ，总时间 $O(n\log n)$ ；额外空间 $O(1)$ ；不稳定。它的最坏时间有保证。

把序列分成两半，分别排好，再用两个指针线性合并。合并时每次取两边当前较小者，循环不变量是输出区已经有序且包含两边所有已取元素。

递归层数 $O(\log n)$ ，每层合并总工作 $O(n)$ ，因此总时间 $O(n\log n)$ 。通常需要 $O(n)$ 辅助数组；相等时优先取左半区可保持稳定。

归并思想同样适用于链表和外排序。

选择枢轴，通过一趟划分让较小元素位于左侧、较大元素位于右侧，枢轴到达最终位置；再递归处理两侧。

平均时间 $O(n\log n)$ ，但若每次划分极不平衡，递归会退化为 $O(n^2)$ 。随机枢轴、三数取中和小区间改用插入排序，都能改善实际表现。

快速排序原地性好、缓存友好，通常很快，但普通实现不稳定，递归栈平均 $O(\log n)$ 、最坏 $O(n)$ 。

若关键字分布范围适合，可以先按值域映射到若干桶，在桶内排序，再依次收集。它利用关键字结构而不只依赖比较；性能取决于桶划分是否均匀以及值域假设。

算法	最好	平均 / 最坏	额外空间	稳定
直接插入	$O(n)$	$O(n^2)$	$O(1)$	是
简单选择	$O(n^2)$	$O(n^2)$	$O(1)$	否
冒泡	$O(n)$	$O(n^2)$	$O(1)$	是
希尔	依增量	依增量	$O(1)$	否
堆排序	$O(n\log n)$	$O(n\log n)$	$O(1)$	否
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n)$	是
快速排序	$O(n\log n)$	平均 $O(n\log n)$ ，最坏 $O(n^2)$	递归栈	否

先写明“一趟结束后什么已经确定”，再逐趟记录序列。插入排序确定有序前缀；选择排序确定最小元素位置；冒泡确定最大元素位置；堆排序确定末尾最大元素；快速排序确定枢轴位置；归并排序确定合并段有序。

只写最后结果无法体现算法过程，也最容易把不同排序混在一起。