快速排序及时间复杂度

/**
 * 快速排序
 * avg： 2NlnN
 * best: nlgn 每次正好对半分
 * worst: (n^2)/2
 * Created by tjc on 2018/7/27.
 */
public class Quick {

    public static void sort(Comparable[] a) {
        {
            //随机打乱数组
        }
        sort(a, 0, a.length - 1);

    }

    private static void sort(Comparable[] a, int lo, int hi) {
        //切分后 a[0],a[1],...,a[j-1] < a[j]
        //a[j+1],a[j+2],a[n] > a[j]
        int j = partition(a, lo, hi);
        //进行递归,分治
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        //选取头元素a[lo]做中位数
        Comparable v = a[lo];
        while (less(a[++i], v)) if (j == hi) break;
        while (less(v, a[--j])) if (j == lo) break;
        if (i >= j) exch(a, i, j);
        return j;
    }

    private static void exch(Comparable[] a, int i, int j) {
        //交换a[i],a[j]
    }

    private static boolean less(Comparable a, Comparable b) {
        //a<b return true
        //else
        //return false
    }
}

改进算法

三向切分

应用于含有大量重复元素的数组，分为大于，等于，小于切分元素的数组

public class Quick3way {

    // This class should not be instantiated.
    private Quick3way() { }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
        assert isSorted(a);
    }

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

三向切分的示意图