快速排序

快速排序选择一个基准值，把数组分成“小于基准值”和“大于等于基准值”两部分，再递归处理两边。平均时间复杂度为 O(n log n)，分区在原数组内完成；如果基准值持续落在区间端点，时间复杂度会退化到 O(n²)。

可以把基准值看成分界员：区间内的数依次经过它，小的移到左边，其余留在右边。扫描结束后，基准值站到两组之间。这个位置已经确定，之后只需处理它的左右两侧。

快速排序如何分区

本课使用 Lomuto 分区，始终选择当前区间末尾的 arr[hi] 作为基准值。j 从 lo 扫描到 hi − 1；i 指向“小于基准值”区域之后的第一个位置，等待下一个较小元素。

当 arr[j] < pivot，交换 arr[j] 与 arr[i]，再让 i 前进一步。当 arr[j] >= pivot，i 不动，只有 j 继续扫描。扫描结束时，i 左侧都小于基准值，i 到 hi − 1 都大于等于基准值。

最后交换 arr[i] 与 arr[hi]，把基准值放到分界处。partition 返回这个位置 p。递归处理的区间是 arr[lo..p−1] 和 arr[p+1..hi]，两边都排除已经归位的基准值。

这里使用严格比较 <。等于基准值的元素会留在右侧，而跨越多个位置的交换可能改变相等元素的先后顺序。因此，快速排序不稳定。

快速排序逐步演示

默认输入为 [38, 12, 56, 7, 12, 41, 23]。把原下标 1 的 12 记作 12a，原下标 4 的 12 记作 12b，就能区分值相同的两个元素。

第一次分区：[0..6]，基准值为 23。 j = 0 时，38 不小于 23，留在右侧。j = 1 时，12a 小于 23，交换到下标 0，i 变为 1。56 留在右侧；7 交换到下标 1；12b 交换到下标 2；41 留在右侧。最后把 23 交换到下标 3，数组变为 [12a, 7, 12b, 23, 56, 41, 38]。下标 3 的位置从此不再改变。

第二次分区：左侧 [0..2]，基准值为 12b。 12a 与基准值相等，不满足 <，留在右侧。7 小于 12b，交换到下标 0，得到 [7, 12a, 12b]。最后交换基准值与下标 1 的元素，得到 [7, 12b, 12a]。两个 12 的位置对调了：数值有序，相等元素的原始顺序却没有保住。

随后，[0..0] 和 [2..2] 都是单元素区间，直接返回。右侧 [4..6] 为 [56, 41, 38]，基准值 38 比前两个数都小，因此交换到下标 4，得到 [38, 41, 56]。子区间 [5..6] 选择 56，它已处于最终位置。结果为 [7, 12b, 12a, 23, 38, 41, 56]。

动画下方的色带对应分区状态：左侧是已确认的 < pivot 区域，中间是扫描过的 >= pivot 区域，剩余部分还没有检查。基准值归位并变绿，表示又一个位置完成排序。

时间与空间复杂度

本课采用末尾基准值，没有随机化。每次分区若接近均分，递归约有 log n 层，每层扫描的元素总数为 O(n)。如果每次选到区间最小值或最大值，一次只能确定一个元素，递归深度接近 n，总比较次数便达到 O(n²)。

已经有序的数组也会触发这种退化。实际实现常用随机基准值或三数取中，降低遇到连续失衡分区的机会，但最坏时间复杂度仍为 O(n²)。分区虽然原地执行，递归栈也占空间，不能把总额外空间写成 O(1)。

边界情况

• 空区间或单元素区间：直接返回。基准值落在边界时，也会产生空区间。
• 已经有序或逆序：末尾元素总是极值，分区持续失衡，时间复杂度退化为 O(n²)。
• 重复值：能按数值排好，但不保证相等元素的原始顺序。默认输入中的两个 12 就会对调。
• 全部等于基准值：都进入 >= pivot 区域，每次只归位一个基准值，也是普通 Lomuto 分区的平方级输入。

常见错误

• 递归区间写成 [lo..p] 或 [p..hi]：包含了已经归位的基准值；区间可能不再缩小，导致无限递归。两侧都应排除 p。
• 漏掉最后的基准值交换：没有 arr[i] ↔ arr[hi]，返回的下标就不对应基准值的位置。
• 每比较一次就增加 i：i 是较小元素区域的边界，只在接收一个较小元素后移动。
• 随意把 < 改成 <=：相等元素会全部进入左侧，分区结果和失衡方向也会改变。
• 把数值有序当成稳定：稳定性比较的是相等元素的身份顺序。需要保留这种顺序时，可以选择归并排序。