08 排序
排序是 408 数据结构的收官章，也是稳定性 + 复杂度总表必须一字不差背下来的地方。本章按"简单 → 分治 → 计数 → 外部"推进，核心资产是一张总表和一次快排 partition 手算。
稳定性定义：相等元素排序后相对次序不变。为什么重要：多关键字排序要"先按次要键排、再按主要键稳定排"——不稳定算法会毁掉前面的排序成果（数据库 ORDER BY 多列的现实需求）。
一、插入排序家族
直接插入：像整理扑克牌
第 i 张牌向前比较，比它大的都往后挪一格，插入。
- 最好（已有序）O(n)，最坏（逆序）O(n²)，平均 O(n²)；稳定
- 数据基本有序时它是最快的 O(n) 级算法——所以混合排序（Timsort）里负责小段
折半插入：只省比较不省移动
插入位置用折半找（O(log n)），但移动次数不变，总量仍 O(n²)。稳定。
希尔排序：分组插入
按增量 d 分组做插入排序，d 逐轮减半到 1——先宏观粗调、最后微调，把"逆序对"提前消灭。
- 复杂度 O(n^1.3) 左右（依增量序列，408 只记"约 n^1.3，最坏 O(n²)"）；不稳定
- ⚠️ 希尔是唯一"分组"的插入排序，选择题常拿它和快排的"分治"混淆——希尔没有递归
二、交换排序家族
冒泡：一轮把最大顶到末尾
相邻逆序就交换，一轮冒一个最大值。加 swapped 标志，已有序时一轮就停 = O(n)。平均 O(n²)；稳定。
快速排序 ⭐（必考）
分治思想：选一个基准 pivot，一趟 partition 把数组切成"≤ pivot | pivot | ≥ pivot"三段，递归两侧。
一趟 partition 手算（挖坑法）：对 {49, 38, 65, 97, 76, 13, 27}，pivot = 49：
初始: [49, 38, 65, 97, 76, 13, 27] pivot=49, low=0, high=6
1. high 找 <49: 27 → 填坑 low: [27, 38, 65, 97, 76, 13, _] low=0
2. low 找 >49: 65 → 填坑 high: [27, 38, _, 97, 76, 13, 65] high=2
3. high 找 <49: 13 → 填坑 low: [27, 38, 13, 97, 76, _, 65] low=2
4. low 找 >49: 97 → 填坑 high: [27, 38, 13, _, 76, 97, 65] high=3
5. low==high=3 → pivot 放 3 号位
结果: [27, 38, 13, 49, 76, 97, 65] ← 一趟结束，49 归位第 4 位 ✅
- 平均 O(n log₂n)（每趟 O(n)，log n 层递归）；空间 O(log₂n)（递归栈）
- 最坏 O(n²)：序列已有序/逆序 + 固定取首元素为 pivot（每层只切出 1 个）→ 解药：三数取中 / 随机选 pivot
- 不稳定（如 [3a, 3b, 2]：3b 可能被换到 3a 前面）
- 划分越平衡越快——理想每次对半切；这也是它和归并的本质差别（快排先干活后递归，归并先递归后干活）
三、选择排序家族
简单选择：每轮挑最小放前面
比较 O(n²) 次雷打不动（无论有序与否），移动最多 O(n)。不稳定（例：[3a, 3b, 1] 一轮后 3b 跑到 3a 前）。
堆排序 ⭐
完全二叉树顺序存储（树性质 5：i 的孩子 2i、2i+1）当优先队列：
- 大根堆（父 ≥ 子）排升序：建堆 → 堆顶（最大）与末尾交换 → 堆大小减 1、向下调整（sift-down） → 循环
- 建堆 O(n)：从最后一个非叶结点 ⌊n/2⌋ 倒序调整；每次调整 O(log n)，总共 O(n log₂n) 雷打不动（最坏也是）
- 不稳定；空间 O(1)
- ⚠️ 手算题：给序列建大根堆，画树、从 ⌊n/2⌋ 结点开始逐个下沉——口算顺序：先看最后一片"父-双子"，从后往前
- 💡 "Top K 大问题用小根堆维护 K 个元素" = 堆排序思想的应用，刷题理模型 高频
四、归并排序与基数排序
归并（2 路归并）⭐
分治到单元素，两两有序合并：
- 最好最坏平均都是 O(n log₂n)；空间 O(n)（辅助数组）；稳定——它是"稳定 + O(n log n)"的唯一常规选择
- 手算：{49,38,65,97,76,13,27} 第 2 趟归并后 = 4 组各 2 元素内部有序：[38,49,65,97,13,76,27]？注意第 1 趟 [38,49],[65,97],[13,76],[27]——27 落单；第 2 趟 [38,49,65,97],[13,27,76]——"第 k 趟后子序列长 2^k"，408 常考"第 2 趟后的状态"
基数排序：不比较，按位分桶
LSD（最低位优先）：按个位分桶 → 按桶序收集 → 按十位分桶 → …d 轮后有序。
- 复杂度 O(d(n + r))：d 位数、r 基数（十进制 r=10）——与 n 几乎线性，前提是 d、r 不大
- 稳定；空间 O(r)
- ⚠️ 唯一"不基于比较"的排序（计数/桶排序同族）；大题考"分配-收集"过程手写
五、必背总表（408 原题就考这张表的排列组合）
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 折半插入 | O(n log n) | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 冒泡 | O(n) | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 快速 | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ 不稳定 |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | ❌ 不稳定 |
| 堆 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ 不稳定 |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ 稳定 |
| 基数 | O(d(n+r)) | 同左 | 同左 | O(r) | ✅ 稳定 |
记忆钩子：
- 稳定四兄弟：插（直接/折半）、冒、归、基——"插冒归基"（想象插着香（烟）冒烟的鸡）
- 不稳定三 + 希：快、选、堆、希尔——"快些选一堆"（选一堆快的）
- 最坏仍 O(n log n) 的：堆、归并（+基数不比较无此概念）
- 原数组有序时最快：直接插入 / 冒泡（O(n)）；反而最慢：快排（O(n²)）
- 空间 O(n)：归并；O(log n)：快排递归栈；其余 O(1)（基数 O(r)）
各场景选型（面试）
- 通用库排序 → 混合派：Timsort（归并+插入，稳定，Python/Java 对象排序）、Introsort（快排+堆排+插入，C++
std::sort） - 求前 K 大 → 小根堆 O(n log K)
- 整数、位数少 → 基数/计数
- 稳定性硬需求 → 归并系
- 内存塞不下 → 外部排序（见下）
六、外部排序：内存装不下的大文件（一段话）
k 路归并：先把大文件分块读入内存排序成若干有序段（run）写回磁盘，再多路归并。败者树让 k 路归并每次取最小只需 O(log k)；置换-选择排序生成更长的初始段减少归并遍数；最佳归并树（哈夫曼思想的复用，树）安排归并顺序使 I/O 最少。408 只考概念：败者树 / 置换选择 / 最佳归并树三个名词对号入座。
七、盲点自测
- 稳定的四种排序？（插入、冒泡、归并、基数）
- 快排最坏什么时候发生？怎么防？（有序 + 固定 pivot；三数取中/随机）
- 建堆从哪个下标开始？（⌊n/2⌋ 倒序下沉）
- 哪个排序一趟能保证一个元素最终归位？（快排、简单选择、堆（顶元素交换）、冒泡——插入和归并不行）
- "第 2 趟归并后"的子序列长多少？（2²=4）
- 数据基本有序选什么？（直接插入——O(n)）
- 空间 O(1) 且 O(n log n) 且不稳定的？（堆排序）
- Top K 用大根堆还是小根堆？（K 大用小根堆，堆顶是 K 个里最小的，随时可被更大的顶替）
八、动手玩
# 快排挖坑法 partition（对照本文手算）
def quicksort(a, lo=0, hi=None):
hi = len(a) - 1 if hi is None else hi
if lo >= hi: return
pivot, i, j = a[lo], lo, hi # 挖坑：pivot 存起来
while i < j:
while i < j and a[j] >= pivot: j -= 1 # 右边找小的填左坑
a[i] = a[j]
while i < j and a[i] <= pivot: i += 1 # 左边找大的填右坑
a[j] = a[i]
a[i] = pivot # 基准归位
quicksort(a, lo, i-1); quicksort(a, i+1, hi)
arr = [49, 38, 65, 97, 76, 13, 27]
quicksort(arr)
print(arr) # [13, 27, 38, 49, 65, 76, 97]
# 亲手验证"第 2 趟归并后子序列长 4"
import math
def merge_pass_state(a, k): # k=2^趟数
return [sorted(a[i:i+k]) for i in range(0, len(a), k)]
print(merge_pass_state([49,38,65,97,76,13,27], 4))
# [[38,49,65,97],[13,27,76]] —— 组内有序，正好是"第 2 趟后"的状态
参考资料
- 王道《数据结构考研复习指导》第 8 章——总表 + 手算题的标准口径
- 《算法图解》第 4 章——快排与 D&C 的图解
- 08-IO管理——外部排序与磁盘 I/O 的配合
- 刷题理模型——排序/堆题单（合并 K 个链表、数组第 K 大、手撕快排）
🏁 基础与理论六大分区至此全部完成：速览、信息表示、操作系统、计算机网络、计算机组成原理、数据结构——408 四门齐了。从理论到实战，下一站：刷题理模型（算法刷题的感悟体笔记，与本章配套使用）。算法是数据结构的延伸——算法区已重制为独立分区，正式入口 00-算法，逐章对应的板子见 总览"通往算法"锚点处。
💬 评论