[TOC]

algorithm 4th(2.3)快速排序

快速排序

注意事项：partition的一次划分可以找出第k（0<k<a.length）小的数。partition的返回值下标所定位的元素，已经就位。

// 只能对实现Comparable接口的数据类型排序
private static void sort(Comparable[] a) {
    sort(a, 0, a.length - 1);
    assert isSorted(a);
}

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);
    assert isSorted(a,lo,hi);
}

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;
}

private static boolean isSorted(Comparable[] a) {
    return isSorted(a, 0, a.length);
}

private static boolean isSorted(Comparable[] a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; ++i) {
        if (less(a[lo], a[lo - 1])) {
            return false;
        }
    }
    return true;
}

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

private static boolean less(Comparable v1, Comparable v2) {
    return (v1.compareTo(v2) < 0);
}

private static void show(Comparable[] a) {
    for (Comparable comparable : a) {
        System.out.print(comparable+" ");
    }
}
//第k小的数
public static Comparable select(Comparable[] a, int k) {
    if (k < 0 || k >= a.length) {
        throw new IllegalArgumentException("index is not between 0 and " + a.length + ": " + k);
    }
    int lo = 0, hi = a.length - 1;
    while (hi > lo) {
        int i = partition(a, lo, hi);
        if      (i > k) hi = i - 1;
        else if (i < k) lo = i + 1;
        else return a[i];
    }
    return a[lo];
}