今天學(xué)習(xí)另外一種更加常用的排序算法：快速排序。

題目介紹

還是使用之前的題目：給定一個(gè)數(shù)組，將數(shù)組按從小到大順序排序。題目理解起來也是很容易的，就不再畫圖介紹了。

歸并排序

快速排序的核心思想是，在數(shù)組中隨機(jī)選擇一個(gè)元素，然后遍歷數(shù)組，將小于該元素的移動到元素左邊，大于該元素的移動到元素的右邊。
然后再分別遞歸對左右兩邊的數(shù)組進(jìn)行排序，最終當(dāng)待排序只有一個(gè)元素時(shí)退出遞歸。

實(shí)現(xiàn)代碼

因在之前文章實(shí)現(xiàn)過排序抽象類，因此快速排序類只要繼承抽象類即可。

public class Quick extends AbstractSort {

    @Override
    public void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    private void sort(Comparable[] a, int lo, int hi) {

        if (lo <= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private int partition(Comparable[] a, int lo, int hi) {
        int i = lo, 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;
    }
}

算法相關(guān)實(shí)現(xiàn)源碼地址：https://github.com/xiekq/rubs-algorithms