青峰科技
19小時前
快速排序算法是分治算法技術(shù)的一個實例，也稱為分區(qū)交換排序?？焖倥判虿捎眠f歸調(diào)用對元素進行排序，是基于比較的排序算法中的一個著名算法，也是面試?？嫉囊粋€算法。

本文主要思想借鑒于這篇文章：

白話經(jīng)典算法系列之六 快速排序 快速搞定

http://blog.csdn.net/morewindows/article/details/6684558
時間復(fù)雜度：

時間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O（1）
性能：

假設(shè)快速排序的復(fù)雜度為T(n) 且所有元素都不相同。T(n) 取決于兩個子問題的規(guī)模，而規(guī)模又取決于中樞點。

最好情況：每個劃分把數(shù)組分成相等的兩部分。時間復(fù)雜度為（nlogn）；
最壞情況：每個劃分把數(shù)組分成不相等的兩部分。時間復(fù)雜度為（n^2）,最壞情況發(fā)生在序列已經(jīng)排序且選擇最后一個元素作為中樞點。
平均情況下的時間復(fù)雜度與最好情況一樣也為（nlogn）；
基本思想：

書上說該算法主要由以下四步組成：

如果數(shù)組中僅有一個元素或者沒有元素需要排序，則返回。
選擇數(shù)組中的一個元素作為中樞點（通常選擇數(shù)組最左邊的元素）。
把數(shù)組分成兩部分，一部分元素大于中樞點，一部分元素小于中樞點。
對兩部分?jǐn)?shù)組遞歸調(diào)用該算法。
借鑒參考文章，在這里我們巧妙的把它翻譯為這樣一種思想：

挖坑填數(shù)、分而治之。

操作過程如下：

假設(shè)有如下數(shù)組，且擬定有一個數(shù)組 A[4,6,2,9,1,17] ，下標(biāo)為index，和兩個指針 left 和 right，和一個保存中樞點的變量 temp。

初始時，取第一個元素為中樞點，此時：left = 0; right = 5; temp = A[left] = 4;

由于已經(jīng)將A[0]中的數(shù)保存到temp中，可以理解成在數(shù)組A[0]上挖了個坑，可以將其它數(shù)據(jù)填充到這來。

1、首先從右向左，尋找第一個比temp小的數(shù)，準(zhǔn)備填充到A[0]的位置上。

當(dāng)right=4時滿足情況，于是將A[4] 挖走，填充到上一個坑A[0]處，并且left++；此時：left=1；right=4；temp=4；形成新坑A[4]。

2、開始從左往右，尋找第一個比temp大的數(shù)，準(zhǔn)備填充到A[4]的位置上。當(dāng)left=1時，便滿足條件，于是將A[1]挖走，填到上一個坑A[4]處，并且right–；此時：left=1；right=3；temp=4；形成新坑A[1];

3、開始從右往左，尋找第二個比temp小的數(shù)，準(zhǔn)備填充到A[1]的位置上。

當(dāng)right=2時滿足情況，于是將A[2] 挖走，填充到上一個坑A[1]處，并且left++；此時：left=2；right=2；temp=4；形成新坑A[2]。

4、此時left=right，則第一趟排序結(jié)束，將temp填充到中樞點index=2的位置上，可以看到，4的左邊都比4小，右邊都比4大。

5、得到新的中樞點后，遞歸對左邊和右邊重復(fù)上述過程即可完成整個排序。

對挖坑填數(shù)進行總結(jié)（引用自上述參考文章）：

1．i =L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個坑a[i]。

2．j–由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個坑a[i]中。

3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中。

4．再重復(fù)執(zhí)行2，3二步，直到i==j，將基準(zhǔn)數(shù)填入a[i]中。
算法實現(xiàn)（java）：

public static void sort(int[] A,int l,int r){ int left=l; int right=r; // index為下標(biāo)，temp用來保存中樞位置的值，無關(guān)數(shù)組A,只是一個臨時變量而已
測試程序：

public static void main(String[] arg){ // TODO Auto-generated method stub
打印內(nèi)容如下：

耗時：9659