前言

排序算法的成本模型计算的是比较和交换的次数。less()方法对元素进行比较，exch()方法将元素交换位置。

1
2
3
4
5
6
7
8
9
private static boolean less(Comparable v, Comparable w) {
   return (v.compareTo(w) < 0);
}

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

思路

快速排序是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立地排序。

快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。前者的递归调用发生在处理整个数组之前，而后者的递归调用则发生在处理整个数组之后。

实现过程

快速排序

基本算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Quick {
    public static void sort(Comparable[] a) {
        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 void shuffle(T[] nums) {
        List<Comparable> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }
}

该方法的关键在于切分。

切分方法

一般策略是先随意地取a[lo]作为切分元素，即那个将会被排序的元素，然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此交换它们的位置。如此继续，我们就可以保证左指针i的左侧元素都不大于切分元素，右指针j的右侧元素都不小于切分元素。当两个指针相遇时，我们只需要将切分元素a[lo]和左子数组最右侧的元素（a[j]）交换然后返回j即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    Comparable v = a[lo];
    while (true) { 
        while (less(a[++i], v)) {
            if (i == hi) break;
        }
        
        while (less(v, a[--j])) {
            if (j == lo) break;
        }

        if (i >= j) break;
        exch(a, i, j);
    }
    exch(a, lo, j);
    return j;
}

这个过程使得数组满足下面三个条件：

  • 对于某个j，a[j]已经排定
  • a[lo]到a[j-1]中的所有元素都不大于a[j]
  • a[j+1]到a[hi]中的所有元素都不小于a[j]

切分方法

复杂度分析

快速排序的最好情况是每次都正好将数组对半分。在这种情况下快速排序所用的比较次数正好满足分治递归的Cn=2Cn/2+n。2Cn/2表示将两个子数组排序的成本，n表示用切分元素和所有数组元素进行比较的成本，这个递归公式的解Cn~nlogn。（下文有具体数学推导）

而在最坏情况下，切分不平衡使得第一次从最小的元素切分，第二次从第二小的元素切分，如此继续，每次切分后两个子数组之一总是为空的，比较次数为(n - 1) + (n - 2) +...+ 1 = n × (n - 1 ) / 2。

而对于空间复杂度来说，主要考虑的是递归调用使用的栈空间，在最好的情况下（也就是对半分），递归深度为logn，最坏情况下的递归深度为n。

  • 最坏时间复杂度 О(n²)
  • 最优时间复杂度 O(nlogn)
  • 平均时间复杂度 O(nlogn)
  • 最坏空间复杂度 O(n)
  • 最优空间复杂度 O(logn)
  • 不稳定

最优时间复杂度的数学证明

数学证明

算法改进

切换到插入排序

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。

只需要将代码中的if (hi <= lo) return;改为if (hi <= lo + M) {Insertion.sort(a, lo, hi); return;}。

三取样切分

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。人们发现取 3 个元素并将大小居中的元素作为切分元素的效果最好。

三向切分法

从左到右遍历数组一次，维护一个指针lt使得a[lo…lt-1]中的元素都小于v，一个指针gt使得a[gt+1…hi]中的元素都大于v，一个指针i使得a[lt..i-1]中的元素都等于v，a[i..gt]中的元素都还未确定。

三向切分法

一开始i和lo相等，对a[i]进行三向比较：

  • a[i]小于v，将a[lt]和a[i]交换，将lt和i加一
  • a[i]大于v，将a[gt]和a[i]交换，将gt减一
  • a[i]等于v，将i加一

对于包含大量重复元素的数组，它将排序时间从线性对数级降低到了线性级别。

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
public class Quick3way {
    public static void sort(Comparable[] a) {
        shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        Comparable v = a[lo];
        int i = lo + 1;
        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++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
    }

	private void shuffle(T[] nums) {
        List<Comparable> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }
}

参考资料