Skip to content

快速排序

基本原理

快速排序的核心思想是：

  1. 选择一个"切分元素"（pivot）
  2. 将数组分为三部分：小于切分元素的部分、切分元素本身、大于切分元素的部分
  3. 递归地对小于和大于切分元素的两部分进行排序

当递归到足够小的子数组时，排序完成。不同于归并排序在合并两个有序子数组时需要额外工作，快速排序的优势在于子数组排序完成后，整个数组自然就是有序的。

切分（Partition）过程

切分是快速排序最关键的步骤，其目标是：

  • 选定一个切分元素v（通常选第一个元素）
  • 重新排列数组，使所有小于v的元素在v的左侧，所有大于v的元素在v的右侧
  • 返回切分元素的最终位置

基本实现思路：

  • 从左向右扫描，找到大于等于切分元素的项
  • 从右向左扫描，找到小于等于切分元素的项
  • 交换这两项
  • 重复上述过程直到左右指针相遇

基本实现代码

public class Quick {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a); // 随机打乱数组，避免最坏情况
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi); // 切分
        sort(a, lo, j-1);  // 排序左半部分
        sort(a, j+1, hi);  // 排序右半部分
    }

    // 切分方法
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1; // 左右扫描指针
        Comparable v = a[lo];   // 切分元素
        while (true) {
            // 扫描左边，找到大于等于v的元素
            while (less(a[++i], v))
                if (i == hi) break;

            // 扫描右边，找到小于等于v的元素
            while (less(v, a[--j]))
                if (j == lo) break;

            // 指针相遇时退出循环
            if (i >= j) break;

            // 交换元素
            exch(a, i, j);
        }

        // 将切分元素放入正确位置
        exch(a, lo, j);
        return j; // 返回切分元素的索引
    }

    // 辅助方法：比较两个元素
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    // 辅助方法：交换两个元素
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

性能特点

  1. 时间复杂度：

    • 平均情况：O(n log n)
    • 最坏情况：O(n²)（当数组已排序或逆序排序时）
    • 最好情况：O(n log n)

    • 空间复杂度：

    • O(log n)（递归调用栈的空间）

    • 优点：

    • 原地排序（不需要额外的大数组）

    • 平均性能优秀
    • 内循环简短，比较次数少

    • 缺点：

    • 对特定输入（如已排序数组）性能退化

    • 不稳定排序（相等元素的相对顺序可能改变）

算法改进

1. 切换到插入排序

对于小规模子数组（通常小于5-15个元素），使用插入排序会更有效率：

private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo + M) { 
        Insertion.sort(a, lo, hi); 
        return; 
    }
    int j = partition(a, lo, hi);
    sort(a, lo, j-1);
    sort(a, j+1, hi);
}

2. 三取样切分

不总是选择第一个元素作为切分元素，而是从子数组中取3个元素，并使用其中值为切分元素。这样切分更加平衡，减少最坏情况的出现概率。

3. 三向切分

当数组中有大量重复元素时，三向切分的快速排序效率更高，将数组分成小于、等于和大于切分元素的三部分：

private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo) return;
    int lt = lo, i = lo+1, gt = hi;
    Comparable v = a[lo];
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if (cmp < 0) exch(a, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else i++;
    }
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);
}

对于包含大量重复元素的数组，三向切分快速排序的复杂度可从O(n log n)降至O(n)，成为"熵最优"排序算法，其复杂度更接近于输入数组的信息量。