Chap12 排序

1、学习目标

排序是数据结构和算法分析的综合复盘：向量、堆、递归、分治、下界、稳定性、原地性都会在这里重新出现。

模块	要掌握的内容
排序指标	时间、空间、稳定性、原地性、适用场景
快速排序	轴点、划分、递归、随机化、重复元素
选择问题	第 `k` 小、快速选择、线性选择
希尔排序	间隔序列、插入排序推广、逆序对
综合对比	冒泡、插入、选择、归并、堆、快排、桶/基数

2、资料范围

PDF 课件	内容
`12.Sorting.A1-A5.Quicksort`	快速排序、性能、重复元素、变种
`12.Sorting.B1-B6.Selection`	选择问题、快速选择、线性选择
`12.Sorting.C1-C4.Shellsort`	希尔排序、逆序对、间隔序列

3、排序指标

评价排序算法时，至少看五件事：

指标	问题
最好/平均/最坏时间	是否有退化风险
额外空间	是否原地
稳定性	相等元素相对次序是否保持
数据敏感性	是否利用基本有序
工程常数	缓存、分支、移动代价

稳定性例子：

1 2	(张三, 90), (李四, 90) 按分数排序后若张三仍在李四前面，则排序稳定。

稳定性在多关键字排序中很重要：先按次关键字稳定排序，再按主关键字稳定排序，可以得到组合排序效果。

4、快速排序

快速排序是分治：

选一个轴点。
将小于轴点的放左边，大于轴点的放右边。
递归排序左右区间。

void quickSort(vector<int>& a, int lo, int hi) {
    if (hi - lo < 2) return;
    int mi = partition(a, lo, hi);
    quickSort(a, lo, mi);
    quickSort(a, mi + 1, hi);
}

4.1 划分

划分的目标不是把整个区间排好，而是让轴点归位：

1	[lo, mi) <= pivot <= (mi, hi)

一次划分复杂度 O(n)。如果每次都接近均分，递归深度 O(log n)，总复杂度 O(n log n)。

4.2 性能

情况	复杂度	原因
最好	`O(n log n)`	每次均分
平均	`O(n log n)`	随机输入或随机轴点
最坏	`O(n^2)`	每次划分极不平衡
空间	平均 `O(log n)`	递归栈

最坏情况常见于已经有序、逆序、或轴点选择固定且数据分布特殊。

4.3 随机化

随机选轴点可以把“特定输入导致退化”的风险转成概率问题：

1 2	int pivotIndex = lo + rand() % (hi - lo); swap(a[lo], a[pivotIndex]);

随机化不是改变最坏复杂度上界，而是降低遇到最坏划分的概率。

4.4 重复元素

大量重复元素会让普通二路划分效率变差。三路划分把区间分成：

1	< pivot \| == pivot \| > pivot

这样重复元素不再反复参与递归，适合数据值域较小或重复率很高的场景。

5、选择问题

选择问题：不完整排序，只找第 k 小元素。

朴素做法：

全排序后取第 k 个，复杂度 O(n log n)。
维护大小为 k 的堆，复杂度 O(n log k)。
快速选择，平均 O(n)。

快速选择和快排类似，只递归一边：

划分后轴点位置为 mi：
若 k == mi，答案就是轴点；
若 k < mi，只在左侧找；
若 k > mi，只在右侧找。

平均复杂度为 O(n)，最坏仍可能 O(n^2)。

6、线性选择

线性选择用更稳的轴点选择策略保证最坏 O(n)。经典思路是 median of medians：

每 5 个元素分成一组。
组内排序，取每组中位数。
递归找这些中位数的中位数。
用它作为轴点划分。
只递归进入包含第 k 小的那一边。

这个算法常数较大，工程中不一定比随机快速选择更快；但理论意义很重要：选择问题可以在线性时间内完成。

7、希尔排序

希尔排序是插入排序的推广。插入排序在基本有序时很快，希尔排序先用大间隔让远距离元素移动，再逐步缩小间隔，最后做间隔为 1 的插入排序。

流程：

1 2	gap = n / 2, n / 4, ..., 1 每个 gap 下，对相隔 gap 的子序列做插入排序

直觉：

大 gap 快速减少远距离逆序。
小 gap 精细调整局部顺序。
最后一轮插入排序面对的是较有序序列。

希尔排序复杂度和间隔序列强相关。它通常原地、不稳定，代码短，实际表现常优于简单 O(n^2) 排序。

8、排序算法对比

算法	平均时间	最坏时间	空间	稳定	备注
冒泡排序	`O(n^2)`	`O(n^2)`	`O(1)`	是	教学意义多
插入排序	`O(n^2)`	`O(n^2)`	`O(1)`	是	基本有序时好
选择排序	`O(n^2)`	`O(n^2)`	`O(1)`	否	交换次数少
归并排序	`O(n log n)`	`O(n log n)`	`O(n)`	是	稳定，适合链表/外排
堆排序	`O(n log n)`	`O(n log n)`	`O(1)`	否	最坏有保障
快速排序	`O(n log n)`	`O(n^2)`	`O(log n)`	否	工程常用，需防退化
希尔排序	依 gap	依 gap	`O(1)`	否	插入排序改进
桶/基数排序	可线性	依条件	依桶	可稳定	非比较排序

9、复盘重点

排序复习时，不要把所有算法混成一团。可以按问题来记：

问题	对应算法
基本有序、小数组	插入排序
需要稳定且 `O(n log n)`	归并排序
要原地且最坏 `O(n log n)`	堆排序
平均性能优先	快速排序
只找第 `k` 小	快速选择
整数范围较小	计数/桶排序
多关键字段或定长整数	基数排序

10、易错点

易错点	修正
快排划分后左右都包含轴点	轴点归位后不再递归
认为随机快排不会最坏	仍有最坏，只是概率低
找第 `k` 小还完整排序	可用快速选择
把线性选择当常用工程方案	理论强，常数较大
希尔排序稳定	间隔移动会破坏相等元素相对次序
只背时间复杂度	稳定性、空间、数据分布也要看

11、复盘清单

检查项	状态
能说出排序稳定性的意义	待复盘
能手动完成一次快排划分	待复盘
能解释快排最坏情况来源	待复盘
能写快速选择的递归逻辑	待复盘
能说明线性选择为什么能保证最坏 `O(n)`	待复盘
能比较归并、堆排、快排的优缺点	待复盘
能解释希尔排序为什么先大 gap 再小 gap	待复盘