演算法-快速排序演算法

快速排序演算法是分治演算法技術的一個實例，也稱為分區交換排序。快速排序採用遞歸調用對元素進行排序，是基於比較的排序演算法中的一個著名演算法，也是面試常考的一個演算法。

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

白話經典演算法系列之六 快速排序 快速搞定

http://blog.csdn.net/morewindows/article/details/6684558

時間複雜度：

• 時間複雜度：O(nlogn)

• 空間複雜度：O（1）

性能：

假設快速排序的複雜度為T(n) 且所有元素都不相同。T(n) 取決於兩個子問題的規模，而規模又取決於中樞點。

• 最好情況：每個劃分把數組分成相等的兩部分。時間複雜度為（nlogn）；

• 最壞情況：每個劃分把數組分成不相等的兩部分。時間複雜度為（n^2）,最壞情況發生在序列已經排序且選擇最後一個元素作為中樞點。

• 平均情況下的時間複雜度與最好情況一樣也為（nlogn）；

基本思想：

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

1. 如果數組中僅有一個元素或者沒有元素需要排序，則返回。

2. 選擇數組中的一個元素作為中樞點（通常選擇數組最左邊的元素）。

3. 把數組分成兩部分，一部分元素大於中樞點，一部分元素小於中樞點。

4. 對兩部分數組遞歸調用該演算法。

借鑒參考文章，在這裡我們巧妙的把它翻譯為這樣一種思想：

挖坑填數、分而治之。

操作過程如下：

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

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

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

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

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

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

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

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

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

5、得到新的中樞點後，遞歸對左邊和右邊重複上述過程即可完成整個排序。

對挖坑填數進行總結（引用自上述參考文章）：

1．i =L; j = R; 將基準數挖出形成第一個坑a[i]。

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

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

4．再重複執行2，3二步，直到i==j，將基準數填入a[i]中。

演算法實現（java）：

public static void sort(int[] A,int l,int r){ int left=l; int right=r; // index為下標，temp用來保存中樞位置的值，無關數組A,只是一個臨時變數而已

測試程序：

public static void main(String[] arg){ // TODO Auto-generated method stub

列印內容如下：

耗時：9659

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！