企业官网建设流程全解析

快速排序（Quick Sort）速记模板

一、核心思想

Quick Sort = 分治 + partition
选pivot，把数组分成：左 ≤ pivot，右 ≥ pivot，然后递归左右。

二、标准流程（必背）

1. 选 pivot（常用 Median-of-Three）

2. partition：左右扫描交换

3. pivot归位

4. 递归左右子数组

三、复杂度（超级重点）

最好：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 → i++

• A[j] > pivot → j--

• A[i] = pivot → 停止交换

✔ 作用：保证均衡划分 ❌ 错误做法：跳过相等 → 会退化 O(N²)

八、快排本质性质

✔ 不稳定
✔ 原地排序
✔ 平均最快排序
✔ 分区算法决定性能

九、inversion（逆序对）关系

一次 partition：

• pivot左侧全部 ≤ pivot

• pivot右侧全部 ≥ pivot

👉 inversion会减少，但不是完全消除
👉 减少量取决于 pivot 位置

十、典型考试结论

✔ pivot越接近中位数越好
✔ 每次partition至少确定一个元素最终位置
✔ 快排 = “不断确定pivot最终位置”

十一、真题讲解

1.【2024-2025 R2-20】

问：第二次partition后不可能的结果？

核心判断：

Quick Sort性质：

• pivot左侧必须 ≤ pivot

• pivot右侧必须 ≥ 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 和 Right

5.【2018-2019 2-3】

输入：{46,79,56,38,40,84}

pivot = 最左46

partition过程：

• 左区：≤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 = 桶数（如10）

LSD关键点

✔ 从低位到高位
✔ 必须稳定排序
✔ 每一趟都是桶排序

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 cycles

4.【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（间接排序）

⭐ 三、复杂度速记

⭐ 四、LSD核心

✔ 从低位到高位
✔ 必须稳定
✔ 每趟桶排序

⭐ 五、一句话总结

比较排序的本质是决策树，因此存在 Ω(N log N) 下界；要突破必须利用“键结构”（桶/基数）。

这个是基数排序（Radix Sort）里的两个核心模式，考试非常爱考对比。

我用最简+好记版给你讲清楚：

🔴 LSD vs MSD 是什么？

🟢 1. LSD（Least Significant Digit）最低位优先

👉 从“右边（低位）”开始排序

比如：三位数

329 457 657 839 436 720

LSD流程：

第1趟：按个位排序

看最后一位

第2趟：按十位排序

第3趟：按百位排序

⭐ LSD核心一句话：

从低位到高位，一轮一轮稳定排序

🟢 特点：

✔ 必须“稳定排序”（非常重要）
✔ 实现简单（循环）
✔ 工程中常用

🟢 适用：

• 固定长度数字
• 字符串排序
• 学生考试成绩ID等

🔵 2. MSD（Most Significant Digit）最高位优先

👉 从“左边（高位）”开始排序

同样例子：

329 457 657 839 436 720

MSD流程：

第1趟：按百位分组

→ 分桶（0-9）

例如：

• 3xx：329, 436
• 4xx：457
• 6xx：657
• 7xx：720
• 8xx：839

然后对每个桶递归排序：

比如 3xx 内部再按十位排序……

⭐ MSD核心一句话：

从高位开始“分组递归”，逐步细化排序

🟢 特点：

✔更像“递归分治”
✔ 可以提前终止（某些桶已经有序）
❌ 实现复杂
❌ 不如LSD稳定易写

🔥 LSD vs MSD 对比（必背）

🧠 一句话记忆

👉 LSD：从右往左“逐位排”
👉 MSD：从左往右“先分组再递归”

🎯 考试常考点

❗1. LSD必须稳定 因为后面高位排序要建立在低位结果基础上

❗2. LSD = 一趟趟桶排序 MSD = 递归桶排序

❗3. LSD适合外排序/工程实现 MSD适合理解递归结构