快速排序的思路

核心思想

分治：每次选一个 pivot，把数组分成”比它小”和”比它大”两部分，然后递归处理两边。

[3, 1, 4, 1, 5, 9, 2, 6]
         ↓ 选 pivot = 3
[1, 1, 2] | 3 | [4, 5, 9, 6]
     ↓               ↓
  递归排            递归排

pivot 一旦放到正确位置，就永远不动了——这是快排的关键性质。

---

代码框架

def quick_sort(arr, lo, hi):
    if lo >= hi:
        return
    p = partition(arr, lo, hi)   # pivot 归位，返回其下标
    quick_sort(arr, lo, p - 1)
    quick_sort(arr, p + 1, hi)

partition 的常见写法（lomuto 方案）：

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

i 维护”比 pivot 小的区域的右边界”，遍历结束后把 pivot 换到 i 位置。

---

复杂度

情况	时间	原因
平均	O(n log n)	每次大致对半分
最坏	O(n²)	pivot 每次选到最大/最小值（已排序数组）
空间	O(log n)	递归栈深度

最坏情况可以通过随机选 pivot 规避：

import random
def partition(arr, lo, hi):
    r = random.randint(lo, hi)
    arr[r], arr[hi] = arr[hi], arr[r]   # 随机换到末尾
    # 后续和 lomuto 一样

---

与二叉树前序遍历的关系

快排的递归过程本质上就是对一棵隐式二叉搜索树做前序遍历：

• 当前节点 = pivot 归位（先处理根）
• 左子树 = 递归左半段
• 右子树 = 递归右半段

理解这个映射，快排的代码结构就不再需要死记——它就是前序遍历的形状。

→ 见二叉树前序遍历