排序是面试必考题。冒泡 O(n²) 慢但好懂；快排 O(n log n) 平均最快；归并稳定 O(n log n)；堆排 O(n log n) 原地不占额外空间；桶/基数排接近 O(n)。这一页把时间空间稳定性和适用场景一张表讲透。
别急着背代码，先按这四步建立直觉：
冒泡：相邻两两比，大的往后冒，每轮冒出一个最大值。慢但好写。
快排：选一个基准 pivot，把比它小的放左、大的放右（分区），再递归排左右。平均 O(n log n)，实际最快。
归并：先对半分到底，再把两个有序小数组合并成大数组。稳定，O(n log n)，但要 O(n) 额外空间。
堆排：建大顶堆，反复把堆顶最大值换到末尾。原地 O(n log n)，但不稳定。
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | 是 |
| 选择 | O(n²) | O(n²) | O(1) | 否 |
| 插入 | O(n²) | O(n²) | O(1) | 是 |
| 快排 | O(n log n) | O(n²) | O(log n) | 否 |
| 归并 | O(n log n) | O(n log n) | O(n) | 是 |
| 堆排 | O(n log n) | O(n log n) | O(1) | 否 |
| 基数/桶 | O(n) | O(n) | O(n+k) | 是 |
选 pivot（常取末元素），用指针 i 记录"小于 pivot 区"的末尾。遍历 j：若 arr[j]<pivot，i++ 并交换 arr[i]、arr[j]。最后交换 arr[i+1] 与 pivot。一轮后 pivot 归位，左右递归。
| 考法 | 出题形式 | 应对 |
|---|---|---|
| 复杂度 | 问平均/最坏 | 背总表 |
| 稳定性 | 问哪个稳定 | 归并冒泡插入基数 |
| 快排最坏 | 什么情况 O(n²) | 已排序+坏 pivot |
| 选型 | 按场景选算法 | 稳定大数据→归并 |
真题基础1. 下列哪个排序是稳定的？
真题中档2. 快速排序的平均时间复杂度是？
真题中档3. 归并排序相比快排的主要特点是？
真题拔高4. 对已排序数组用末位元素做 pivot 快排，复杂度退化为？
| 天 | 任务 | 自检 |
|---|---|---|
| 第 1 天 | 读②③④，背排序总表 | 复杂度全对 |
| 第 2 天 | 背稳定性 + 基础 1-6 | 稳定的记牢 |
| 第 3 天 | 做中档 7-12，手推快排分区 | pivot 归位对 |
| 第 4 天 | 做拔高 13-18，理解外部排序 | 能讲清归并多路 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书默写排序总表 | 不看资料全默对 |