中等排序 · 快排
快速排序 图解题解
这道题到底在问什么
选基准 pivot → partition 一趟把数组分成「小于 pivot ｜ pivot ｜ 不小于 pivot」→ 对左右两段递归。
- 输入
- [3, 6, 1, 5, 2, 4]
- 输出
- [1, 2, 3, 4, 5, 6]
最优解：一步一步想明白
- 3冒泡、选择每趟扫一整遍才安顿一个数，n 趟就是 O(n²)。快排的提速点：partition 一趟同样只定一个数（基准），但顺手把数组切成两段独立子问题，规模对半砍，于是平均只要 log n 层。
- 4取末尾当基准，用边界 i 指「小区的末尾」。指针 j 从左扫到倒数第二个：遇到比基准小的，就把它换进小区（i 先前进一格再交换）。扫完，i+1 左边全小于基准、右边全不小于——把基准换到 i+1，它就永久归位了。
- 5pivot = 4 · i = −1基准 pivot＝最后一个数 4（下标 5，橙色）。边界 i 初始在 −1（小区还空）。j 从下标 0 开始扫，把小于 4 的换进左边小区。
- 6i: −1 到 0看下标 0 的 3：3 小于 4，i 前进到 0，下标 0 和自己交换（原地）。小区现在是 [3]。
- 7i 不动 = 0看下标 1 的 6：6 不小于 4，跳过，i 不动——这是 partition 的负例分支：不小于基准的元素留在原地，等基准归位后自然落到右段。
- 8i: 0 到 1 · swap(1,2)看下标 2 的 1：1 小于 4，i 前进到 1，把下标 1（当前是 6）和下标 2 的 1 交换。小区扩成 [3,1]，6 被甩到了后面。
- 9i 不动 = 1看下标 3 的 5：5 不小于 4，跳过，i 仍在 1。
- 10i: 1 到 2 · swap(2,4)看下标 4 的 2：2 小于 4，i 前进到 2，把下标 2（当前是 6）和下标 4 的 2 交换。小区＝[3,1,2]，扫描结束。
- 11swap(3,5) · 4 归位把基准 4 和 i+1=3 交换：4 已归位到下标 3。它左边 [3,1,2] 全小于 4、右边 [6,5] 全不小于 4。partition 返回基准下标 3。
- 12在 [0,2] 上重复对左半 [3,1,2] 做一模一样的 partition（递归），排成 [1,2,3]。左边整段（含已归位的 4）全部有序。
- 13done再对右半 [6,5] 递归，排成 [5,6]。两半都有序，整体 [1,2,3,4,5,6] 完成——递归的本质就是「在子数组上重复同一套 partition」。
- 16快排的灵魂是 partition——每趟让基准「一步到位」，并把问题切成两个独立子问题。这块积木复用极广：「找第 K 大」的快速选择就是只递归其中一半，三路快排是把它扩成三段。
⚠️ 容易写错的地方
✗ 错：基准归位写 a[i], a[hi] = ...
✓ 对：基准归位到 i+1：a[i+1], a[hi] = ...
i 停在「最后一个小于基准的元素」上，i+1 才是小区右侧第一个空位，写成 i 会把一个小元素换到右段、基准也没真正归位
✗ 错：基准固定取首/尾，遇有序退化
✓ 对：随机选基准或三数取中，再换到末尾
对已排好的数组固定取末尾，每趟划分极不均，退化成 O(n²)
✗ 错：递归区间含基准本身
✓ 对：递归 [lo, i] 和 [i+2, hi]
基准已永久归位，再让它参与划分是重复劳动，区间也会越界
完整代码（Python）
Python
def quicksort(a, lo, hi):
if lo >= hi: return # 区间只剩 0/1 个，天然有序
pivot = a[hi]; i = lo - 1 # 基准取末尾，i 是小区末尾
for j in range(lo, hi):
if a[j] < pivot: # 比基准小才换进小区
i += 1; a[i], a[j] = a[j], a[i]
a[i+1], a[hi] = a[hi], a[i+1] # 基准归位到 i+1
quicksort(a, lo, i); quicksort(a, i+2, hi) # 只递归两侧，跳过基准套路模板 · 快排 partition（背下来）
def partition(a, lo, hi):
pivot, i = a[hi], lo - 1
for j in range(lo, hi):
if a[j] < pivot: # 小的换进左区
i += 1; a[i], a[j] = a[j], a[i]
a[i+1], a[hi] = a[hi], a[i+1] # 基准归位
return i + 1 # 基准最终下标复杂度
时间复杂度
平均 O(n log n)
每次划分约对半，log n 层、每层共扫 n 个；最坏 O(n²)（划分极不均）
空间复杂度
O(log n)
原地交换，额外开销只有递归栈，深度约 log n
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 快速排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「快排」，换最直接的暴力解会差在哪？+
快排抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。