快速排序

发表于   |   分类于

简介

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

优点：原地排序（只需要一个很小的辅助栈），且将长度为 N 的数组排序所需的时间和 NlogN 成正比；
缺点：非常脆弱，在实现时要非常小心才能避免低劣的性能。

Basic Plan

  • Shuffle the array.
  • Partition so that, for some j
    • entry a[j] is in place
    • no larger entry to the left of j
    • no smaller entry to the right of j
  • Sort each piece recursively.

代码

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
public class Quick {
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        while (true) {
            // find item on left to swap
            while (less(a[++i], a[lo]))
                if (i == hi) break;
                
            // find item on right to swap
            while (less(a[lo], a[--j]))
                if (j == lo) break;
                
            // check if pointer cross
            if (i >= j) break;
            
            // swap
            exch(a, i, j);
        }
        
        // swap with partitioning item
        exch(a, lo, j);
        
        // return index of item now known to be in place
        return j;
    }
    
    public static void sort(Comparable[] a) {
        // shuffle needed for performance guarantee
        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);
    }
}

Quicksort trace

Quicksort properties

  • Quicksort is an in-place sorting algorithm.
  • Quicksort is not stable.