题目描述
选基准 pivot → partition 把数组分成「<pivot | pivot | ≥pivot」→ 对左右两段递归。
思路解析
取最后一个数 3 当基准。用一个边界 i 指"小区的末尾"。扫描其余元素：遇到比基准小的，就把它换到小区里(i 前进)。扫完，把基准换到小区后面——它左边全 <3、右边全 ≥3，基准归位。
选基准 = 3 (最后一个)：基准 pivot = 3(下标 5，橙色)。开始扫描前面的元素，把小于 3 的归到左边。
遇到 2 < 3 · 换入左区：扫到 2 < 3，把它换到左区(和当前左区末尾交换)。左区现在 = [2]。
遇到 1 < 3 · 换入左区：8 不小于 3 跳过；扫到 1 < 3，换进左区。左区 = [2,1]。9 也不小，跳过。
基准归位 · 3 放到左区后面：扫描结束，把基准 3 换到左区后面(下标 2)。现在 3 已归位：左边 [2,1] 全 <3、右边 [5,9,8] 全 ≥3。
左半 partition · 基准取 1：对左半 [2,1] 做同样的 partition：基准取 1。扫描 2 不比 1 小，所以基准 1 直接归位到最前。递归就是"在子数组上重复一模一样的过程"。
递归左半完成 → [1,2]：左半排成 [1,2]，左边整段(含已归位的基准 3)全部有序。
递归右半 [5,9,8] → [5,8,9]：对右半 [5,9,8] 同样递归，排成 [5,8,9]。两半都有序，整体 [1,2,3,5,8,9] 完成。
快排的灵魂是 partition——每趟让基准"一步到位"，并把问题切成两个独立子问题。"找第 K 大(快速选择)"就是只递归其中一半。
参考代码（Python）
1def quicksort(a, lo, hi):
2 if lo >= hi: return
3 pivot = a[hi]; i = lo - 1 # i: 小区末尾
4 for j in range(lo, hi):
5 if a[j] < pivot: # 比基准小
6 i += 1; a[i], a[j] = a[j], a[i]
7 a[i+1], a[hi] = a[hi], a[i+1] # 基准归位
8 quicksort(a, lo, i); quicksort(a, i+2, hi) # 递归两半复杂度分析
- 时间复杂度：平均 O(n log n) —— 最坏 O(n²)（每次划分极不均）
- 空间复杂度：O(log n) —— 递归栈
套路模板
记住骨架：基准取末位、i 守小区边界、j 扫描遇小就换、最后基准归位返回其下标。快速选择、三路快排都从它变化。
1def partition(a, lo, hi):
2 pivot, i = a[hi], lo - 1
3 for j in range(lo, hi):
4 if a[j] < pivot: # 小的换进左区
5 i += 1; a[i], a[j] = a[j], a[i]
6 a[i+1], a[hi] = a[hi], a[i+1] # 基准归位
7 return i + 1 # 基准最终下标易错点
- ❌ 基准固定取首/尾遇有序退化 → ✅ 随机选基准或三数取中（已排序数据下固定基准会 O(n²)）
- ❌ 递归区间含基准本身 → ✅ 递归 [lo,i] 和 [i+2,hi]（基准已归位，不该再参与划分）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。