快速排序

冒泡、选择每趟扫一整遍才安顿一个数，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 大」的快速选择就是只递归其中一半，三路快排是把它扩成三段。