Algorithm · Sorting
比较排序的两大路线与线性排序的破局：快排/归并/堆排的取舍 · 稳定性 · 工业混合排序（Timsort / pdqsort）
快排（平均最快）· 归并（稳定+链表友好）· 堆排（O(1) 空间）——同是 O(n log n)，性格迥异
计数/桶/基数不比较元素，突破 Ω(n log n) 下界——条件是值域可枚举
没有一种排序统治所有输入——Timsort/pdqsort 都是"混合三明治"
The Big Table
| 算法 | 平均 | 最坏 | 空间 | 稳定 | 一句话记忆点 |
|---|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | ✓ | 相邻逆序交换，教学专用 |
| 选择 | O(n²) | O(n²) | O(1) | ✗ | 每轮选最小放前面，交换次数最少 |
| 插入 | O(n²) | O(n²) | O(1) | ✓ | 近乎有序时 O(n+d)——工业排序的基石 |
| 希尔 | O(n^1.3) | 依增量 | O(1) | ✗ | 分组插入，插排的"预热版" |
| 归并 | O(n log n) | O(n log n) | O(n) | ✓ | 稳定 + 链表天然友好 + 外部排序 |
| 快排 | O(n log n) | O(n²) | O(log n) | ✗ | 平均最快，靠随机枢轴防退化 |
| 堆排 | O(n log n) | O(n log n) | O(1) | ✗ | 唯一最坏 O(n log n) 且原地 |
| 计数 | O(n+k) | O(n+k) | O(k) | ✓（稳定版） | 值域 [0,k] 直接数个数 |
| 桶 | O(n+k) | O(n²) | O(n+k) | ✓（桶内稳定） | 均匀分布时线性；桶内再排 |
| 基数 | O(d(n+k)) | 同左 | O(n+k) | ✓ | 按位稳定排序 d 轮（d=位数） |
Bubble · Selection · Insertion
// 插入排序：把 a[i] 插入左侧有序段 func insertionSort(a []int) { for i := 1; i < len(a); i++ { x := a[i] j := i - 1 for j >= 0 && a[j] > x { a[j+1] = a[j] // 右移腾位 j-- } a[j+1] = x } }
逻辑最直白（相邻逆序就换），但交换次数 = 逆序对数、常数大；唯一亮点是"一轮无交换即有序"的早停。教学价值 > 工程价值。
每轮全局找最小、只交换一次（交换次数 O(n) 最少），但远距离交换会打乱相等元素——[5a,5b,2] → [2,5b,5a]，稳定性破产。这也是它比冒泡更少被用的原因。
原地、稳定、常数极小、对有序输入自适应；缺点只有"远距离搬移慢"。所以 pdqsort/Timsort 在子区间 ≤16~32 时全部切换到插入排序。
按增量分组做插入排序、增量逐步缩小——先让大跳跃搬远距离元素，最后一轮在"近乎有序"上收尾。增量序列决定复杂度，无公认最优。
Merge Sort · Stable Workhorse
// 归并：分治 + 线性合并 func mergeSort(a []int, tmp []int, l, r int) { if r-l <= 1 { return } m := l + (r-l)/2 mergeSort(a, tmp, l, m) mergeSort(a, tmp, m, r) // 合并两个有序段 → tmp → 拷回 i, j, k := l, m, l for i < m || j < r { if j >= r || (i < m && a[i] <= a[j]) { tmp[k] = a[i]; i++ } else { tmp[k] = a[j]; j++ } k++ } copy(a[l:r], tmp[l:r]) } // a[i] <= a[j] 取等号 → 稳定性的来源
① 最坏也是 O(n log n)（无退化输入）；② 稳定（合并时相等取左段）；③ 顺序访问——链表排序（LC 148）与外部排序（磁盘数据）的唯一正解。
O(n) 辅助数组（可优化到 O(n) 恰好一次分配）；对内存数组的缓存局部性不如快排。逆序对计数（LC 493/剑指 51）是它的招牌衍生题：合并时统计跨段逆序。
自底向上（迭代）归并：无递归栈；归并树/归并平衡树是竞赛向延伸。Timsort = 归并 + 插入的工业混合（第 10 页）。
T(n) = 2T(n/2) + O(n) → Case 2 → Θ(n log n)——主定理的标准案例（复杂度 deck）。
Quick Sort · Partition
// Lomuto 分区 + 随机枢轴 func quickSort(a []int, l, r int) { if l >= r { return } p := partition(a, l, r) quickSort(a, l, p-1) quickSort(a, p+1, r) } func partition(a []int, l, r int) int { // 随机化：防已序输入退化 idx := l + rand.Intn(r-l+1) a[idx], a[r] = a[r], a[idx] pv := a[r]; i := l - 1 for j := l; j < r; j++ { if a[j] < pv { i++ a[i], a[j] = a[j], a[i] } } a[i+1], a[r] = a[r], a[i+1] return i + 1 }
期望 Θ(n log n)（随机枢轴，任何输入下成立）；最坏 Θ(n²)——每次枢轴都切出 1:n−1（已序输入 + 取端点）。随机化把最坏从"输入决定"变成"概率事件"。
① 随机枢轴；② 三数取中（首中尾取中位数，对抗已序/逆序）；③ 三向切分（Dutch flag，< = > 三段）——大量重复元素时从 O(n log n) 降到 O(n)。
递归栈深度。工程优化：只递归小区间、大区间用循环（尾递归消除），栈深保证 O(log n)。
Lomuto 好写、交换多；Hoare 双向扫描交换更少、对重复元素更友好——工业实现基本都用 Hoare 变体。三种分区的可背代码与边界陷阱见 快速排序手撕 deck。
Lomuto Partition · Step By Step
Heap Sort · Why Quicksort Wins
① 建堆 O(n)（自底向下沉，堆 deck 的招牌推导）；② n−1 次"堆顶换到末尾 + 下沉"每次 O(log n)。总计 O(n log n)、O(1) 空间、最坏有界——三项都占，但实践中仍输给快排。
① 缓存局部性：堆排的父子下标 i→2i 距离越走越远，跳跃访问 cache miss；快排 partition 顺序扫描。② 分支可预测：堆排比较结果决定两个孩子谁大，分支抖动。③ 快排的两段递归天然适配硬件预取。
① 需要最坏 O(n log n) 且内存极限（嵌入式）；② 只需要前 k 个（TopK 不用排完）；③ 优先队列场景的副产品。Introsort 的兜底：快排递归过深时切堆排——用它"最坏有界"这一项。
快排：平均最快、通用首选。归并：稳定 + 链表/外部排序。堆排：空间最省 + 最坏有界。没有全能冠军，只有场景匹配。
| 维度 | 快排 | 归并 | 堆排 |
|---|---|---|---|
| 平均时间 | O(n log n) 最快常数 | O(n log n) | O(n log n) |
| 最坏时间 | O(n²)（需随机化） | O(n log n) | O(n log n) |
| 空间 | O(log n) 栈 | O(n) | O(1) |
| 稳定性 | ✗ | ✓ | ✗ |
| 缓存/分支 | 顺序扫描，最友好 | 较好 | 跳跃访问，最差 |
| 工业角色 | 主引擎（pdqsort） | 稳定需求 + Timsort 骨架 | 兜底 + TopK |
Counting · Bucket · Radix
Ω(n log n) · Decision Tree
① 比较排序的每次决策只有"小于/不小于"两个分支 → 执行过程是一棵二叉决策树；② n 个元素有 n! 种排列，每种都要一个叶子才能区分 → 叶子数 ≥ n!；③ 二叉树高 h ≥ log₂(n!)，Stirling 近似 log₂(n!) ≈ n log₂n − 1.44n → Ω(n log n)。
快排/归并/堆排都是 n log n——已经贴住下界，比较模型内没有渐近改进空间了；工程优化只能在常数与缓存上做文章（这正是 pdqsort 们的战场）。
计数/桶/基数不做两两比较——它们利用"值是有限集合中的整数"这一额外信息直接定位。信息量来自值域结构，不在决策树模型内，下界管不着。
"那能不能把任意类型都排到 O(n)？"——不能：任意可比较类型只有两两比较可用；"值域无限大的整数呢？"——位数 d 随 n 增长时基数排序退回 n log n 量级。
| 问题 | 下界 | 突破条件 |
|---|---|---|
| 比较排序 | Ω(n log n) | 放弃比较（计数/基数） |
| 找最大最小 | Ω(n)（3n/2 次配对更优） | — |
| 基于比较的第 k 小 | Ω(n) | —（quickselect 贴住） |
| 排序 n 个互异整数（字长 w） | Ω(min(n log n, n·w)) | 字排序/整数排序研究前沿 |
Timsort · Introsort · pdqsort
识别天然有序的 run（升/降段），run 用插入排序补长到 minrun，再用归并合并 runs + galloping 加速。最好 O(n)（已有序）、最坏 O(n log n)、稳定——为真实世界的"部分有序"数据而生。
快排开头 + 递归深度超 2log n 切换堆排（保最坏）+ 小区间插入排序收尾。取快排的平均快、堆排的最坏有界、插排的小数据常数。
pattern-defeating quicksort：快排骨架 + 坏 partition 检测（切分极不均则换堆排/打乱枢轴）+ 重复元素三向切分 + 短区间插排 + 已有序/逆序 O(n) 检测。不稳定，Go 1.19 起 sort.Sort/sort.Slice 换装 pdqsort（slice.go 的 pdqsort 函数）。
sort.Slice（反射 + pdqsort，不稳）· sort.SliceStable（插入+归并，稳）· Go 1.21+ slices.Sort（泛型无反射，更快）——slices 优先。
| 实现 | 配方 | 承诺 |
|---|---|---|
| Timsort | 插入（run 内）+ 归并（runs） | 稳定 · 最坏 O(n log n) · 最好 O(n) |
| Introsort | 快排 + 堆排兜底 + 插排收尾 | 最坏 O(n log n) · 不稳定 |
| pdqsort | 快排 + 坏 case 检测 + 三向 + 插排 | 最坏 O(n log n) · 最好 O(n) · 不稳定 |
| 基数+计数控 | 整数专用 | O(n) 级，看位宽 |
Stability Matters
稳定 = 相等元素排序后保持原相对顺序。稳定：冒泡/插入/归并/计数（稳定版）/桶/基数；不稳定：选择/希尔/快排/堆排。记"插冒归计桶基稳，选希快堆不稳"。
先按次要键排序、再按主要键稳定排序 → 次要键顺序在主键相同时自动保留。基数排序的正确性完全建立在稳定性上（按位排序必须保序才有意义）。
订单按金额排，同金额的按下单时间——若排序不稳定，同样的输入两次结果都不同（非确定性），测试和排障都痛苦。
SQL 标准里 ORDER BY 对相等行不保证顺序——想要确定序必须补第二关键字。这是"稳定性"概念在工程里最常见的坑。
① 比较器带上原始下标做 tie-breaker；② 换稳定算法。前者 O(1) 额外代价，最常用。
| 场景 | 为什么在乎 / 不在乎 |
|---|---|
| 基本类型排序 | 不在乎——相等元素不可区分 |
| 结构体多键排序 | 在乎——第二键语义靠它保 |
| 基数排序 | 必需——按位排序的正确性前提 |
| TopK / 判等 | 不在乎——只关心集合/最值 |
| 可复现性要求 | 在乎——稳定=确定性输出 |
Quickselect · LC 215
快排每轮两半都递归 O(n log n)；找第 k 大只需留在枢轴命中的那一边——期望代价 n + n/2 + n/4 + … = 2n = O(n)（几何级数，复杂度 deck）。
堆 O(n log k)、空间 O(k)、支持流式；快选平均 O(n)、空间 O(log n) 栈、但最坏 O(n²)（随机枢轴概率极低）且要全量数据在内存。堆 deck 有完整对比表。
BFPRT / median of medians：五分取中位数的中位数做枢轴，保证最坏 O(n)——理论完美、常数大，工程少见；面试要能说出名字和思想。
LeetCode 215 直接手写 partition 循环；生产上 sort.Slice 排完取下标（O(n log n)）——除非 n 巨大，快选的工程收益有限，说清这个取舍是加分项。
// 第 k 大 = 排序下标 len-k（LC 215） func findKthLargest(a []int, k int) int { target := len(a) - k l, r := 0, len(a)-1 for { p := partition(a, l, r) if p == target { return a[p] } else if p < target { l = p + 1 // 只走右边 } else { r = p - 1 // 只走左边 } } } // 期望 O(n) · 空间 O(1) 迭代版 // partition 复用快排的（随机枢轴）
LeetCode Shortlist
| 考法 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 裸手写 | 912 排序数组 M | 快排会 TLE 的坑（重复元素）→ 三向切分或堆排/归并 |
| 结构上排序 | 148 排序链表 M · 147 链表插入排序 M | 148 = 归并 + 快慢指针，链表排序唯一正解 |
| TopK / 选择 | 215 第K大 M · 347 前K高频 M · 703 数据流第K大 E | 快选 / 堆双解法都要会 |
| 区间/拼接 | 56 合并区间 M · 179 最大数 M · 435 无重叠区间 M | 自定义比较器是核心；179 的拼接序数证明 |
| 线性排序应用 | 41 缺失的第一个正数 H · 75 颜色分类 M | 41 = 原地哈希/桶思想；75 = 荷兰国旗三向切分 |
Interview QA · Part 1
枢轴每次切出 1:n−1（已序输入+端点枢轴、大量重复）。防：随机枢轴 / 三数取中 / 三向切分（重复）/ Introsort 深度兜底。
递归深度 = 切分深度，平均 O(log n)、最坏 O(n)。工程优化：每次只递归较小区间、大区间循环处理，栈深严格 O(log n)。
partition 顺序扫描缓存友好、无 O(n) 辅助内存、平均常数最小；配 introsort/pdqsort 兜底最坏。稳定需求才上归并系（Timsort）。
合并时 a[i] <= a[j] 取左段（<= 而非 <）——左段元素在原数组中更靠前，相等时保序。
链表随机访问 O(n)（快排 partition 需要）；归并只需顺序合并，且链表合并 O(1) 额外空间（改指针）、快慢指针找中点 O(n log n) 总账——LC 148 标准解。
实测 2~3 倍：堆排父子跳跃访问 cache miss 多、分支不可预测；快排 partition 顺序扫描 + 预取友好。"渐进同阶、硬件吃亏"是标准表述。
三向切分（< = > 三段，荷兰国旗）：等值段直接排除递归——全相等数组 O(n)；普通快排在这种输入退化到 O(n²)（等值全落一边）。
建堆是高度加权求和 O(n)（堆 deck）；之后 n−1 次下沉每次 O(log n) 占主导 → 总 O(n log n)。"建堆便宜"不等于"排序便宜"。
Interview QA · Part 2
n! 种排列需要 n! 个叶子，二叉树高 ≥ log₂(n!) ≈ n log₂n − 1.44n（Stirling）。每次比较只得 1 bit——信息不够，算法再聪明也没用。
整数且值域 k 可控（如年龄、分数）。稳定版：计数改前缀和确定"每个值在输出中的结束位置"，逆序遍历原数组输出——这是基数排序的子程序。
它不做元素两两比较，而是利用"值可分解为有限位"的结构信息按位稳定排序 d 轮 O(d(n+k))。决策树下界只约束比较模型。
真实数据常有天然有序段（run）：Timsort 识别 run、用插入排序补齐到 minrun、归并时 galloping 跳跃——已有序 O(n)、部分有序按比例省。
Go 1.19 起 sort.Sort/sort.Slice 用 pdqsort（快排+坏 case 检测+三向+插排，不稳定）；SliceStable 稳定；1.21+ 优先 slices.Sort（泛型、无反射开销）。选型：默认 slices，要稳定用 slices.SortStableFunc。
期望工作量 n + n/2 + n/4 + … = 2n；最坏 O(n²)（枢轴每次选到极端）。BFPRT 中位数的中位数保最坏 O(n) 但常数大。
同键业务对象顺序漂移 → 输出不确定、测试难写；多键排序依赖稳定性叠加；基数排序正确性以其为前提。Go 里 SliceStable 与 Slice 的选择就是这道题。
Related & References
快速排序（手撕实现）→（Lomuto / Hoare / 三向切分可背代码 + 完整可运行版）
复杂度分析 →（主定理与下界的信息论语言）
二分查找 →（有序数组的孪生应用）
堆 →（heap sort / TopK 的主场）
贪心 →（区间调度靠"先排序"起手）
堆与优先队列 →（建堆 O(n) 与下沉操作）
数组与链表 →（LC 148 链表归并的地基）
Go slice →（sort API 的操作对象）
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch7/8/9 | 快排与随机化 · 线性排序 · 中位数与顺序统计 |
| go.dev/doc/go1.19 · src/sort/zsortinterface.go | sort 包换装 pdqsort 的官方说明与源码 |
| O. Peters (2021) · pdqsort | pattern-defeating quicksort 原始论文/仓库 |
| T. Peters · Timsort（listsort.txt） | Python listsort 实现注释：run/galloping 设计 |
| LeetCode 912/148/215/56/179/41/75 题解 | 五种考法的代表题 |