数据结构与算法 / 系统课时

快速排序

快速排序

快速排序先分区,再在子区间内排序。枢轴如何选择、等值元素怎么放置,会影响子问题的规模。本课先读经典两段分区的图,再运行能跳过等值区的三向实现。

学习目标

  • 区分两段分区和三向分区的边界。
  • 用不变式解释三向分区每次交换后的状态。
  • 区分随机化的期望时间、最坏时间和栈空间保证。

从两段分区到三向分区

图中是三数取中配合 Lomuto 的两段分区。先从首、中、尾选中间值并将它移到末尾,扫描其余元素,最后归位枢轴。一侧不大于枢轴,另一侧大于枢轴。对于 [9,4,7,3,10,5,1],选择 3 后可得到 [1,3,7,9,10,5,4]。枢轴以外的两侧仍需排序。三数取中只考察三个值,无法保证接近全区间的中位数。全部相等时,图示方案仍可能每次只排除一个元素。 Princeton 快速排序与重复键

快速排序的三数取中与 Lomuto 分区过程

三向分区单独保留等于枢轴的区域。对当前闭区间 [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 的有界随机整数

java
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));
    }
}
text
排序前: [9, 4, 7, 3, 10, 5, 1, 3]
排序后: [1, 3, 3, 4, 5, 7, 9, 10]

时间、栈和稳定性

每轮分区线性扫描当前区间。对互异元素,随机枢轴的期望时间为 Θ(nlog⁡n)\Theta(n\log n);当极端枢轴反复出现时,仍可发生 Θ(n2)\Theta(n^2) 的最坏时间。全等输入的三向实现只需要一轮分区,时间为 Θ(n)\Theta(n)。每次实际递归处理的是非等值的较小段,它至多为当前段一半,因此栈深最坏为 O(log⁡n)O(\log n),这个保证独立于时间是否退化。交换操作会改变某些等键记录的先后关系,所以该分区方法不保证稳定。 Princeton 快速排序分析

本课练习

手推 [2,1,2,3] 以 2 为枢轴的一轮三向分区,标出未知段。再用相同的全等数组比较两段与三向方案的分区次数。下一课讨论任何比较排序共同面对的信息下界。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

快速排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通