【数据结构与算法】快速排序

发表于 | 分类于 | 阅读次数:

快速排序（英语：Quick sort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n 个项目要 $O(n\,log\,n)$ 次比较。在最坏状况下则需要 $O(n^2)$ 次比较，但这种状况并不常见。事实上，快速排序 $O(n\,log\,n)$ 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class QuikSort {

    private QuikSort() {}

    public static void sort(int[] a) {
        // 特殊输入的检查
        if (a == null || a.length <= 1)
            return;
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int lo, int hi) {
        // 退出边界
        if (lo >= hi)
            return;
        int i = partition(a, lo, hi);
        sort(a, lo, i);
        sort(a, i + 1, hi);
    }

    private static int partition(int[] a, int lo, int hi) {
        int p = a[lo]; // 定义中枢元素
        int i = lo + 1;
        int j = hi;
        while (true) {
            // 从左至右找出第一个比中枢元素大的元素
            while (a[i] <= p && i < hi)
                i++;
            // 从优制作找出最后一个比中枢元素小的元素
            while (a[j] > p && j > lo)
                j--;
            // 跳出循环
            if (i >= j)
                break;
            // 交换元素
            swap(a, i, j);
        }
        // 交换元素，使得中枢元素位于合适的位置
        swap(a, lo, j);
        return j;
    }

    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

参考文献