题目描述
选基准 pivot → partition 一趟把数组分成「小于 pivot ｜ pivot ｜ 不小于 pivot」→ 对左右两段递归。
思路解析
冒泡、选择每趟扫一整遍才安顿一个数，n 趟就是 O(n²)。快排的提速点：partition 一趟同样只定一个数（基准），但顺手把数组切成两段独立子问题，规模对半砍，于是平均只要 log n 层。
取末尾当基准，用边界 i 指「小区的末尾」。指针 j 从左扫到倒数第二个：遇到比基准小的，就把它换进小区（i 先前进一格再交换）。扫完，i+1 左边全小于基准、右边全不小于——把基准换到 i+1，它就永久归位了。
选基准＝末尾的 4：基准 pivot＝最后一个数 4（下标 5，橙色）。边界 i 初始在 −1（小区还空）。j 从下标 0 开始扫，把小于 4 的换进左边小区。
j=0 · 3 小于 4 → 换入小区：看下标 0 的 3：3 小于 4，i 前进到 0，下标 0 和自己交换（原地）。小区现在是 [3]。
j=1 · 6 不小于 4 → 跳过（负例）：看下标 1 的 6：6 不小于 4，跳过，i 不动——这是 partition 的负例分支：不小于基准的元素留在原地，等基准归位后自然落到右段。
j=2 · 1 小于 4 → 换入小区：看下标 2 的 1：1 小于 4，i 前进到 1，把下标 1（当前是 6）和下标 2 的 1 交换。小区扩成 [3,1]，6 被甩到了后面。
j=3 · 5 不小于 4 → 跳过：看下标 3 的 5：5 不小于 4，跳过，i 仍在 1。
j=4 · 2 小于 4 → 换入小区：看下标 4 的 2：2 小于 4，i 前进到 2，把下标 2（当前是 6）和下标 4 的 2 交换。小区＝[3,1,2]，扫描结束。
基准归位 · 4 换到 i+1=3：把基准 4 和 i+1=3 交换：4 已归位到下标 3。它左边 [3,1,2] 全小于 4、右边 [6,5] 全不小于 4。partition 返回基准下标 3。
递归左半 [3,1,2] → [1,2,3]：对左半 [3,1,2] 做一模一样的 partition（递归），排成 [1,2,3]。左边整段（含已归位的 4）全部有序。
递归右半 [6,5] → [5,6] · 全部有序：再对右半 [6,5] 递归，排成 [5,6]。两半都有序，整体 [1,2,3,4,5,6] 完成——递归的本质就是「在子数组上重复同一套 partition」。
快排的灵魂是 partition——每趟让基准「一步到位」，并把问题切成两个独立子问题。这块积木复用极广：「找第 K 大」的快速选择就是只递归其中一半，三路快排是把它扩成三段。
参考代码（Python）
1def quicksort(a, lo, hi):
2 if lo >= hi: return # 区间只剩 0/1 个，天然有序
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] # 基准归位到 i+1
8 quicksort(a, lo, i); quicksort(a, i+2, hi) # 只递归两侧，跳过基准复杂度分析
- 时间复杂度：平均 O(n log n) —— 每次划分约对半，log n 层、每层共扫 n 个；最坏 O(n²)（划分极不均）
- 空间复杂度：O(log n) —— 原地交换，额外开销只有递归栈，深度约 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 # 基准最终下标易错点
- 错误写法：基准归位写 a[i], a[hi] = ... → 正确写法：基准归位到 i+1：a[i+1], a[hi] = ...（i 停在「最后一个小于基准的元素」上，i+1 才是小区右侧第一个空位，写成 i 会把一个小元素换到右段、基准也没真正归位）
- 错误写法：基准固定取首/尾，遇有序退化 → 正确写法：随机选基准或三数取中，再换到末尾（对已排好的数组固定取末尾，每趟划分极不均，退化成 O(n²)）
- 错误写法：递归区间含基准本身 → 正确写法：递归 [lo, i] 和 [i+2, hi]（基准已永久归位，再让它参与划分是重复劳动，区间也会越界）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。