coursera上斯坦福的算法專項(xiàng)在講到快速排序時(shí)，稱其為最優(yōu)雅的算法之一酵颁。快速排序確實(shí)是一種比較有效的排序算法月帝，很多類庫中也都采用了這種排序算法躏惋，其最壞時(shí)間復(fù)雜度為，平均時(shí)間復(fù)雜度為嫁赏，且其不需要額外的存儲(chǔ)空間其掂。

基本步驟

快速排序主要使用了分治的思想，通過選取一個(gè)pivot潦蝇，將一個(gè)數(shù)組劃分為兩個(gè)子數(shù)組款熬。其步驟為：
1.從數(shù)組中選擇一個(gè)元素作為pivot
2.重新排列數(shù)組深寥，小于pivot的在pivot的左邊，大于pivot的在其右邊贤牛。
3.遞歸地對(duì)劃分后的左右兩部分重復(fù)上述步驟惋鹅。

簡(jiǎn)單的偽代碼如下：

<img src="http://ou5lyiz64.bkt.clouddn.com/img/qsort%E9%80%89%E5%8C%BA_001.png" style="zoom: 50%" />

其中最主要的就是partition劃分過程了。

劃分過程

partition過程需要首先選擇一個(gè)pivot殉簸，然后將小于pivot的元素放到左半部分闰集，大于pivot的放到右半部分，并且最終pivot的位置及為其在排序好的數(shù)組中的最終位置般卑。

這里使用第一個(gè)元素作為pivot武鲁，若選擇其他元素作為pivot，則將其交換到第一個(gè)元素蝠检，這樣可以保證代碼的一致性及容易實(shí)現(xiàn)沐鼠。示意圖如下：

<img src="http://ou5lyiz64.bkt.clouddn.com/img/qsort%E9%80%89%E5%8C%BA_002.png" style="zoom:50%" />

這里使用i和j，i和j最初為p+1的位置叹谁，在遍歷的過程中i始終指向>p的第一個(gè)元素饲梭，j始終指向當(dāng)前待遍歷的元素，若a[j] < p焰檩，則將其與a[i]進(jìn)行交換憔涉。相關(guān)過程如下:

<img src="http://ou5lyiz64.bkt.clouddn.com/img/qsort%E9%80%89%E5%8C%BA_003.png" style="zoom:50%" />

基本實(shí)現(xiàn)如下：

    /**
    * a[l+1],...,a[i-1] < p
    * a[i],...,a[j-1] > p
    */
    private static int partition(int[] a, int l, int r) {
        int p = a[l];

        int i = l + 1;
        for (int j=l+1; j<=r; j++) {
            if (a[j] < p) {
                swap(a, j, i);
                i++;
            }
        }
        swap(a, l, i-1);
        return i-1;
    }

基本實(shí)現(xiàn)

public class QuickSort {
    public static void qSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }
    
        qSort(a, 0, a.length-1);
    }

    private static void qSort(int[] a, int l, int r)    {
        if (l >= r) {
            return;
        }

        int pos = partition(a, l, r);

        qSort(a, l, pos - 1);
        qSort(a, pos + 1, r);
    }

    /**
    * a[l+1],...,a[i-1] < p
    * a[i],...,a[j-1] > p
    */
    private static int partition(int[] a, int l, int r) {
        int p = a[l];
        int i = l + 1;
        for (int j=l+1; j<=r; j++) {
            if (a[j] < p) {
                swap(a, j, i);
                i++;
            }
        }
        swap(a, l, i-1);
        return i-1;
    }

    //返回pivot下標(biāo) 選擇第一個(gè)元素
    private static int choosePivotFirst(int[] a, int l, int r) {
        return l;
    }
    
   private static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

pivot的選取

根據(jù)斯坦福算法專項(xiàng)課，然我們實(shí)現(xiàn)三種不同的pivot選取方式析苫，并計(jì)算相應(yīng)比較次數(shù)兜叨，分別為choose first, choose last, median of three, 還可以進(jìn)行隨機(jī)選取，這也是快速排序?yàn)槭裁词且环N隨機(jī)化算法藤违。

pivot的選取決定了快速排序的運(yùn)行時(shí)間浪腐，下面對(duì)幾種特殊情況進(jìn)行分析：

1.最壞情況

假設(shè)我們始終選取第一個(gè)元素作為pivot, 并且輸入數(shù)組是有序的，那么每次劃分后面所有元素都大于pivot, 每次只能將問題規(guī)模減少１顿乒，所以運(yùn)行時(shí)間為 = .

2.最好情況

最好情況為每次選取的pivot都能將數(shù)組平均地劃分為兩部分议街，由于劃分的過程為，所以總的運(yùn)行時(shí)間為根據(jù)主方法璧榄，時(shí)間復(fù)雜度為O(nlogn)特漩。

3.隨機(jī)選取

每次運(yùn)行過程中，隨機(jī)選取pivot, 通常能得到比較好的結(jié)果骨杂。

選取方式及實(shí)現(xiàn)

斯坦福算法專項(xiàng)課上讓我們實(shí)現(xiàn)三種不同的選取方式涂身，選取第一個(gè)，最后一個(gè)搓蚪，以及三數(shù)取中蛤售。

1.choose first

該種方式最為簡(jiǎn)單，只需返回子數(shù)組的第一個(gè)元素下標(biāo)即可，下面為其實(shí)現(xiàn)：

//返回pivot下標(biāo) 選擇第一個(gè)元素
private static int choosePivotFirst(int[] a, int l, int r) {
    return l;
}

2.choose last

選擇最后一個(gè)元素悴能，實(shí)現(xiàn)如下：

//選擇最后一個(gè)元素作為pivot
private static int choosePivotLast(int[] a, int l, int r) {
        return r;
}

3.median-of-three

選取第一個(gè)揣钦、最后一個(gè)以及中間的元素的中位數(shù)，如4 5 6 7, 第一個(gè)4, 最后一個(gè)7, 中間的為5, 這三個(gè)數(shù)的中位數(shù)為５, 所以選擇5作為pivot漠酿，8 2 5 4 7, 三個(gè)元素分別為8 5 7, 中位數(shù)為7, 所以選擇最后一個(gè)元素7作為pivot冯凹，其實(shí)現(xiàn)如下：

//median-of-three pivot rule
private static int choosePivotMedianOfThree(int[] a, int l, int r) {    
    int mid = 0;
    if ((r-l+1) % 2 == 0) {
        mid = l + (r-l+1)/2 - 1;
    } else {
        mid = l + (r-l+1)/2;
    }

    //只需要找出中位數(shù)即可，不需要交換
    //有的版本也可以進(jìn)行交換
    if (((a[l]-a[mid]) * (a[l]-a[r])) <= 0) {
        return l;
    } else if (((a[mid]-a[l]) * (a[mid]-a[r])) <= 0)    {
        return mid;
    } else {
        return r;
    }
}

最后的劃分過程如下：

private static int partition(int[] a, int l, int r) {
    //pivot選擇方式
    //int pi = choosePivotFirst(a, l, r);
    //int pi = choosePivotLast(a, l, r);
    int pi = choosePivotMedianOfThree(a, l, r);

    //始終將第一個(gè)元素作為pivot, 若不是, 則與之交換
    if (pi != l) {
        swap(a, pi, l);
    }
    int p = a[l];

    int i = l + 1;
    for (int j=l+1; j<=r; j++) {
        if (a[j] < p) {
            swap(a, j, i);
            i++;
        }
    }
    swap(a, l, i-1);
    return i-1;
}

注意最后的劃分過程相比于之前增加的pivot的選取方式炒嘲，而不是單純地將第一個(gè)元素作為pivot, 可以看到宇姚，若第一個(gè)元素不是pivot, 需要將pivot與第一個(gè)元素進(jìn)行交換，這樣保證代碼的統(tǒng)一性夫凸。

總結(jié)與感想

1.學(xué)會(huì)體會(huì)這些算法背后的思想浑劳，為什么要這樣設(shè)計(jì)

2.對(duì)于比較復(fù)雜的算法，學(xué)會(huì)使用特殊情況進(jìn)行分析

參考資料:

(1) coursera斯坦福算法專項(xiàng)課part1

(2) 維基百科快速排序