数据结构基础——Sorting 快速排序、比较排序下界 + 桶/基数/表排序

快速排序Quick Sort速记模板一、核心思想Quick Sort 分治 partition选pivot把数组分成左 ≤ pivot右 ≥ pivot然后递归左右。二、标准流程必背选 pivot常用 Median-of-Threepartition左右扫描交换pivot归位递归左右子数组三、复杂度超级重点最好O(N log N)均匀划分平均O(N log N)最坏O(N²)每次选到最小/最大四、为什么会退化如果 pivot 每次选极值左边空 / 右边 N−1递归退化成链→ O(N²)五、Median-of-Three考试重点A[L], A[C], A[R] 取中位数作为 pivot作用✔ 避免已排序退化 ✔ 提高平均性能 ✔ 约提升 ~5%六、小数组优化Cutoff当 N ≤ 10~20→ 用 insertion sort 替代 quicksort 原因递归开销大七、相等元素处理超级重点正确做法A[i] pivot → iA[j] pivot → j--A[i] pivot → 停止交换✔ 作用保证均衡划分 ❌ 错误做法跳过相等 → 会退化 O(N²)八、快排本质性质✔ 不稳定✔ 原地排序✔ 平均最快排序✔ 分区算法决定性能九、inversion逆序对关系一次 partitionpivot左侧全部 ≤ pivotpivot右侧全部 ≥ pivot inversion会减少但不是完全消除 减少量取决于 pivot 位置十、典型考试结论✔ pivot越接近中位数越好✔ 每次partition至少确定一个元素最终位置✔ 快排 “不断确定pivot最终位置”十一、真题讲解1.【2024-2025 R2-20】问第二次partition后不可能的结果核心判断Quick Sort性质pivot左侧必须 ≤ pivotpivot右侧必须 ≥ pivot每次partition不会打乱已确定结构检查选项看是否存在❌ 左右违反大小关系❌ pivot分区结构不合法结论B 不可能违反partition结构2.【2023-2024 2-2-1】问一次Median-of-Three后 inversion减少量核心partition后pivot左右完全分开所有跨区逆序对被消除 减少的是“pivot参与的所有跨区逆序对”结论减少量 pivot的“跨越逆序对数” 考试一般选固定数值看pivot位置4.【2017-2018 2-3】问非递归快排用stack存什么核心快排递归结构Qsort(A, Left, Right)所以stack必须保存✔ 子问题范围答案 Left 和 Right5.【2018-2019 2-3】输入{46,79,56,38,40,84}pivot 最左46partition过程左区≤46 → 38,40右区46 → 79,56,84最终结果 40,38,46,79,56,84或等价合法partition结果十二、考试最重要总结必须背⭐ 快排三句话✔ pivot决定效率✔ partition决定结构✔ recursion决定复杂度⭐ 复杂度好O(N log N)平均O(N log N)坏O(N²)⭐ 最重要性质✔ pivot最终位置固定✔ 左小右大✔ 每次减少跨区逆序对⭐ 高频考点✔ Median-of-Three作用✔ stack存Left/Right✔ inversion减少✔ partition合法性判断Quick Sort 通过 pivot 不断划分区间使每次递归都“确定一个元素最终位置”的分治排序算法。比较排序下界 桶/基数/表排序 速记一、比较排序下界必考理论任何基于“比较”的排序算法最坏时间复杂度下界[Ω(N \log N)]证明思路必须会背排序 N 个不同元素 → 有 N! 种排列 比较排序 → 决策树模型 叶子数 ≥ N!二叉树高度 k 满足[2^k ≥ N!] ⇒ k ≥ log(N!) Θ(N log N)一句话总结比较排序 决策树 → 必须区分 N! 种情况 → 下界 Ω(N log N)二、突破 N log N 的方法 必须放弃“比较模型” → 使用“键值结构”三、三大非比较排序1. 桶排序Bucket Sort适用键范围小0 ~ M复杂度[O(N M)]特点✔ 非比较排序 ✔ 计数思想 ❌ M太大则退化2. 基数排序Radix Sort核心按“位”排序LSD或MSD复杂度[O(P(N B))]P 位数B 桶数如10LSD关键点✔ 从低位到高位✔ 必须稳定排序✔ 每一趟都是桶排序3. 表排序Table Sort核心不直接交换元素只排序索引表特点✔ 交换成本低✔ 最后做“循环置换”✔ 最坏移动 ≤ 3N/2四、易错点总结❌ 非比较排序不受 Ω(N log N) 限制❌ LSD必须稳定❌ Bucket/Radix依赖数据范围或位数❌ Table Sort本质是“间接排序”五、真题讲解1.【2016-2017 1-1】“比较排序 best case ≥ O(N log N)”❌ 错原因下界是最坏/平均 Ω(N log N)但 best case 可以是O(N)如Insertion已有序2.【2024-2025 R1-6】LSD一趟后结果是否可能关键LSD第一趟 按个位排序稳定只要满足 ✔ 个位数有序 ✔ 稳定排序结果3.【2023-2024 2-3-1】Table Sort后 index permutation 是 cycle核心✔ Table Sort本质 置换✔ 任何排列 disjoint cycles4.【2016-2017 2-5】LSD第一趟结果步骤只看个位数字排序稳定→ 按个位分桶 → 收集6.【2015-2016 2-6】1-digit numbers O(N)排序方法选项分析quicksort → O(N log N)insertion → O(N²)shell → 不保证线性bucket → ✔ O(N)答案✔ Bucket Sort六、考试核心总结必须背⭐ 一、理论核心✔ 比较排序下界 Ω(N log N)✔ 来源 决策树 N!排列⭐ 二、突破方法✔ bucket范围✔ radix位数✔ table间接排序⭐ 三、复杂度速记方法复杂度比较排序≥ O(N log N)BucketO(N M)RadixO(P(NB))TableO(N)移动⭐ 四、LSD核心✔ 从低位到高位✔ 必须稳定✔ 每趟桶排序⭐ 五、一句话总结比较排序的本质是决策树因此存在 Ω(N log N) 下界要突破必须利用“键结构”桶/基数。这个是基数排序Radix Sort里的两个核心模式考试非常爱考对比。我用最简好记版给你讲清楚 LSD vs MSD 是什么 1. LSDLeast Significant Digit最低位优先 从“右边低位”开始排序比如三位数329 457 657 839 436 720LSD流程第1趟按个位排序看最后一位第2趟按十位排序第3趟按百位排序⭐ LSD核心一句话从低位到高位一轮一轮稳定排序 特点✔ 必须“稳定排序”非常重要✔ 实现简单循环✔ 工程中常用 适用固定长度数字字符串排序学生考试成绩ID等 2. MSDMost Significant Digit最高位优先 从“左边高位”开始排序同样例子329 457 657 839 436 720MSD流程第1趟按百位分组→ 分桶0-9例如3xx329, 4364xx4576xx6577xx7208xx839然后对每个桶递归排序比如 3xx 内部再按十位排序……⭐ MSD核心一句话从高位开始“分组递归”逐步细化排序 特点✔更像“递归分治”✔ 可以提前终止某些桶已经有序❌ 实现复杂❌ 不如LSD稳定易写 LSD vs MSD 对比必背项目LSDMSD方向低位 → 高位高位 → 低位方法逐趟稳定排序递归分桶实现简单复杂是否稳定✔必须稳定依赖实现常见程度⭐⭐⭐⭐⭐⭐⭐ 一句话记忆 LSD从右往左“逐位排” MSD从左往右“先分组再递归” 考试常考点❗1. LSD必须稳定 因为后面高位排序要建立在低位结果基础上❗2. LSD 一趟趟桶排序 MSD 递归桶排序❗3. LSD适合外排序/工程实现 MSD适合理解递归结构