算法笔记五

快速排序

quicksort

public class Quick{
    public class 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);
    }
}

// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    Comparable v = a[lo];
    while (true) { 

        // find item on lo to swap
        while (less(a[++i], v)) {
            if (i == hi) break;
        }

        // find item on hi to swap
        while (less(v, a[--j])) {
            if (j == lo) break;      // redundant since a[lo] acts as sentinel
        }

        // check if pointers cross
        if (i >= j) break;

        exch(a, i, j);
    }

    // put partitioning item v at a[j]
    exch(a, lo, j);

    // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
    return j;
}

快排的轨迹

快排的提升

• 小数组用插入排序

• 正确估计中值

Quick-select

private static Comparable select(Comparable[] a,int k){
    StdRandom.shuffle(a);
    int lo = 0; hi = a.length - 1;
    while(hi > lo){
        int j = partition(a,lo,hi);
        if(j<k){
            lo = j + 1;
        }
        else if(j>k){
            hi = j - 1;
        }
        else 
            return a[k];
    }
    return a[k];
}

Duplicate keys

这节会引出3向切分(荷兰国旗问题)，主要是双向切分i,j向中间相遇时，遇到相同的元素会停住。

We found that qsort is unbearably slow on "organ-pipe" inputs like "01233210":

main (int argc, char**argv) {
 int n = atoi(argv[1]), i, x[100000];
 for (i = 0; i < n; i++)
 x[i] = i;
 for ( ; i < 2*n; i++)
 x[i] = 2*n-i-1;
 qsort(x, 2*n, sizeof(int), intcmp);
}

Here are the timings on our machine:
$ time a.out 2000
real 5.85s
$ time a.out 4000
real 21.64s
$time a.out 8000
real 85.11s

// quicksort the subarray a[lo .. hi] using 3-way partitioning
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);
}

Summary