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

实现

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) {
        sort(a, 0, a.length - 1);
    }

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

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 使用 apache RandomUtils 生成测试数据
*/
public static void main(String[] args) {
    Comparable[] random = new Comparable[20];
    for (int i = 0; i < 20; i++) {
        random[i] = RandomUtils.nextInt(1, 10);
    }
    sort(random);
    for (int i = 0; i < 20; i++) {
        System.out.print(random[i]);
        if (i != random.length - 1) {
            System.out.print(" | ");
        }
    }
    isSorted(random);
}