快速排序：分区过程可视化讲解

目标：理解快速排序分区逻辑：左侧不大于 pivot，右侧不小于 pivot（本页使用 Hoare 双指针）。

橙色 = 基准值 pivot 绿色 = pivot 左侧区间蓝色 = pivot 右侧区间

第一屏：原始数组

第二屏：课堂 quicksort 代码（原样）

public static void quicksort (int[] a, int lo, int hi) {
    if ( hi <= lo ) return;
    int p = partition(a, lo, hi);
    quicksort(a, lo, p-1);
    quicksort(a, p+1, hi);
}

第三屏：快速排序原理（通俗版）

把快速排序理解成“反复做同一件事”：先把一段数字分成左右两边，再分别处理左右两边。

下面这段解释是对第二屏代码的逐行说明，先看清“它在干什么”，再看“为什么这样做”。

第 1 行：if (hi <= lo) return; 区间里只有 0 或 1 个元素时，已经有序，直接结束。
第 2 行：p = partition(a, lo, hi); 在当前区间里做一次“分区”，把数据分成左右两边，并返回 pivot 的最终位置 p。
第 3 行：quicksort(a, lo, p-1); 继续处理 pivot 左边那一段。
第 4 行：quicksort(a, p+1, hi); 继续处理 pivot 右边那一段。

quicksort 的参数是什么意思？（这是最容易忽略的关键点）

a：要排序的数组。
lo：当前处理区间的左边界下标（包含在区间内）。
hi：当前处理区间的右边界下标（包含在区间内）。

partition 的参数是什么意思？（它只处理 a 的一小段）

a：同一个数组，不会创建新数组。
lo：分区的起点下标（包含）。
hi：分区的终点下标（包含）。

重要提示：这两个函数处理的范围都是 lo 到 hi 的闭区间，也就是 lo 和 hi 都要算进去。

第 1 步：选一个基准值 pivot 在当前区间里先挑一个数当“分界线”。本教程里，每次都选最左边的数。

第 2 步：把区间分成两边 让比 pivot 小（或不大于）的数去左边，比 pivot 大（或不小于）的数去右边。

第 3 步：让 pivot 落到正确位置 分区完成后，pivot 左边都不大于它，右边都不小于它，所以它的位置就固定了。

第 4 步：对左右区间重复同样动作 左区间再分一次，右区间再分一次。区间长度变成 0 或 1 时，就不用再处理。

partition 的作用是什么？它只做三件事：选 pivot、让左右分区、返回 pivot 的位置 p。它不会一次就把整段排好，只是把问题拆成更小的左右两段。

quicksort 的作用是什么？它负责“不断对左右两段重复分区”，直到每段都很短（0 或 1 个元素），这时整个数组就有序了。

一句话记忆：选 pivot → 分左右 → pivot 归位 → 递归左右，直到区间足够小。

第四屏：partition 的 3 条规则

规则 1：先选基准值 在当前区间里，最左边数字先作为基准值 pivot。

规则 2：左右指针扫描 左指针找“>= pivot”的元素，右指针找“<= pivot”的元素，找到后交换位置。

规则 3：基准值归位 当左右指针相遇（或交错）时，交换 a[lo] 和 a[j]，基准值落到最终位置 p。

第四屏补充：第一次 partition 逐帧图解（i / j 在上方）

本次是 partition(0, 15)，基准值 pivot 为 49。每一帧都显示完整数组，并标出 i 和 j 的当前位置。

阅读顺序：先看 i/j 指针位置，再看数组变化；i < j 时交换，i >= j 时结束扫描。

第五屏：11 次 partition 全步骤

第六屏：递归树 + 最终结果 + 记忆要点

递归树（文字版）

quicksort(0,15) -> p=11
├─ quicksort(0,10) -> p=0
│  ├─ quicksort(0,-1) 结束
│  └─ quicksort(1,10) -> p=3
│     ├─ quicksort(1,2) -> p=1
│     │  ├─ quicksort(1,0) 结束
│     │  └─ quicksort(2,2) 结束
│     └─ quicksort(4,10) -> p=8
│        ├─ quicksort(4,7) -> p=4
│        │  ├─ quicksort(4,3) 结束
│        │  └─ quicksort(5,7) -> p=6
│        │     ├─ quicksort(5,5) 结束
│        │     └─ quicksort(7,7) 结束
│        └─ quicksort(9,10) -> p=9
│           ├─ quicksort(9,8) 结束
│           └─ quicksort(10,10) 结束
└─ quicksort(12,15) -> p=15
   ├─ quicksort(12,14) -> p=12
   │  ├─ quicksort(12,11) 结束
   │  └─ quicksort(13,14) -> p=13
   │     ├─ quicksort(13,12) 结束
   │     └─ quicksort(14,14) 结束
   └─ quicksort(16,15) 结束

最终有序数组

3 条记忆要点

要点 1：先确定基准值，再完成左右分区。
要点 2：左指针找大于等于 pivot，右指针找小于等于 pivot。
要点 3：先递归左区间，再递归右区间，区间长度小于等于 1 时结束。

课堂小提问（2~3 题）

问题 1：第 1 步里的 pivot 是多少？
问题 2：为什么要先分左右区间再递归？
问题 3：quicksort 的终止条件是什么？