数据结构与算法 / 系统课时
快速排序
快速排序
快速排序先分区,再在子区间内排序。枢轴如何选择、等值元素怎么放置,会影响子问题的规模。本课先读经典两段分区的图,再运行能跳过等值区的三向实现。
学习目标
- 区分两段分区和三向分区的边界。
- 用不变式解释三向分区每次交换后的状态。
- 区分随机化的期望时间、最坏时间和栈空间保证。
从两段分区到三向分区
图中是三数取中配合 Lomuto 的两段分区。先从首、中、尾选中间值并将它移到末尾,扫描其余元素,最后归位枢轴。一侧不大于枢轴,另一侧大于枢轴。对于 [9,4,7,3,10,5,1],选择 3 后可得到 [1,3,7,9,10,5,4]。枢轴以外的两侧仍需排序。三数取中只考察三个值,无法保证接近全区间的中位数。全部相等时,图示方案仍可能每次只排除一个元素。 Princeton 快速排序与重复键

三向分区单独保留等于枢轴的区域。对当前闭区间 [lo,hi],用 lt、i、gt 标记四段。[lo,lt) 小于枢轴,[lt,i) 等于枢轴,[i,gt] 尚未检查,(gt,hi] 大于枢轴。遇到较大值,交换到右端后仍要检查换回来的值,所以只减 gt,不移动 i。未知区域消失后,等值段已到位,两侧分别继续排序。 Princeton 三向分区说明
Java 17 实现
保存为 QuickSortDemo.java。使用当前区间内均匀采样的枢轴。演示传入固定种子便于复现,理论上的期望是对枢轴选择的随机性而言。代码只递归较小一侧,用循环处理较大一侧。执行 javac -encoding UTF-8 --release 17 QuickSortDemo.java,再执行 java QuickSortDemo。 Java Random 的有界随机整数
import java.util.Arrays;
import java.util.Objects;
import java.util.Random;
public class QuickSortDemo {
public static void sort(int[] values, Random random) {
Objects.requireNonNull(values, "values");
Objects.requireNonNull(random, "random");
sort(values, 0, values.length - 1, random);
}
private static void sort(int[] values, int lo, int hi, Random random) {
while (lo < hi) {
int pivot = values[lo + random.nextInt(hi - lo + 1)];
int lt = lo;
int i = lo;
int gt = hi;
while (i <= gt) {
if (values[i] < pivot) {
swap(values, lt++, i++);
} else if (values[i] > pivot) {
swap(values, i, gt--);
} else {
i++;
}
}
if (lt - lo < hi - gt) {
sort(values, lo, lt - 1, random);
lo = gt + 1;
} else {
sort(values, gt + 1, hi, random);
hi = lt - 1;
}
}
}
private static void swap(int[] values, int left, int right) {
int saved = values[left];
values[left] = values[right];
values[right] = saved;
}
public static void main(String[] args) {
int[] values = {9, 4, 7, 3, 10, 5, 1, 3};
System.out.println("排序前: " + Arrays.toString(values));
sort(values, new Random(7));
System.out.println("排序后: " + Arrays.toString(values));
}
}排序前: [9, 4, 7, 3, 10, 5, 1, 3]
排序后: [1, 3, 3, 4, 5, 7, 9, 10]时间、栈和稳定性
每轮分区线性扫描当前区间。对互异元素,随机枢轴的期望时间为 ;当极端枢轴反复出现时,仍可发生 的最坏时间。全等输入的三向实现只需要一轮分区,时间为 。每次实际递归处理的是非等值的较小段,它至多为当前段一半,因此栈深最坏为 ,这个保证独立于时间是否退化。交换操作会改变某些等键记录的先后关系,所以该分区方法不保证稳定。 Princeton 快速排序分析
本课练习
手推 [2,1,2,3] 以 2 为枢轴的一轮三向分区,标出未知段。再用相同的全等数组比较两段与三向方案的分区次数。下一课讨论任何比较排序共同面对的信息下界。