青峰科技
19小時(shí)前
快速排序算法是分治算法技術(shù)的一個(gè)實(shí)例逗柴，也稱為分區(qū)交換排序蛹头。快速排序采用遞歸調(diào)用對(duì)元素進(jìn)行排序嚎于，是基于比較的排序算法中的一個(gè)著名算法掘而，也是面試常考的一個(gè)算法于购。
本文主要思想借鑒于這篇文章：
白話經(jīng)典算法系列之六 快速排序 快速搞定
http://blog.csdn.net/morewindows/article/details/6684558
時(shí)間復(fù)雜度：
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O（1）
性能：
假設(shè)快速排序的復(fù)雜度為T(n) 且所有元素都不相同袍睡。T(n) 取決于兩個(gè)子問(wèn)題的規(guī)模，而規(guī)模又取決于中樞點(diǎn)肋僧。
最好情況：每個(gè)劃分把數(shù)組分成相等的兩部分斑胜。時(shí)間復(fù)雜度為（nlogn）；
最壞情況：每個(gè)劃分把數(shù)組分成不相等的兩部分嫌吠。時(shí)間復(fù)雜度為（n^2）,最壞情況發(fā)生在序列已經(jīng)排序且選擇最后一個(gè)元素作為中樞點(diǎn)止潘。
平均情況下的時(shí)間復(fù)雜度與最好情況一樣也為（nlogn）；
基本思想：
書(shū)上說(shuō)該算法主要由以下四步組成：
如果數(shù)組中僅有一個(gè)元素或者沒(méi)有元素需要排序辫诅，則返回凭戴。
選擇數(shù)組中的一個(gè)元素作為中樞點(diǎn)（通常選擇數(shù)組最左邊的元素）。
把數(shù)組分成兩部分炕矮，一部分元素大于中樞點(diǎn)么夫，一部分元素小于中樞點(diǎn)。
對(duì)兩部分?jǐn)?shù)組遞歸調(diào)用該算法肤视。
借鑒參考文章档痪，在這里我們巧妙的把它翻譯為這樣一種思想：
挖坑填數(shù)、分而治之邢滑。
操作過(guò)程如下：
假設(shè)有如下數(shù)組腐螟，且擬定有一個(gè)數(shù)組 A[4,6,2,9,1,17] ，下標(biāo)為index困后，和兩個(gè)指針 left 和 right乐纸，和一個(gè)保存中樞點(diǎn)的變量 temp。
初始時(shí)摇予，取第一個(gè)元素為中樞點(diǎn)锯仪，此時(shí)：left = 0; right = 5; temp = A[left] = 4;
由于已經(jīng)將A[0]中的數(shù)保存到temp中，可以理解成在數(shù)組A[0]上挖了個(gè)坑趾盐，可以將其它數(shù)據(jù)填充到這來(lái)庶喜。
1小腊、首先從右向左，尋找第一個(gè)比temp小的數(shù)久窟，準(zhǔn)備填充到A[0]的位置上秩冈。
當(dāng)right=4時(shí)滿足情況，于是將A[4] 挖走斥扛，填充到上一個(gè)坑A[0]處入问，并且left++；此時(shí)：left=1稀颁；right=4芬失；temp=4；形成新坑A[4]匾灶。
2棱烂、開(kāi)始從左往右，尋找第一個(gè)比temp大的數(shù)阶女，準(zhǔn)備填充到A[4]的位置上颊糜。當(dāng)left=1時(shí)，便滿足條件秃踩，于是將A[1]挖走衬鱼，填到上一個(gè)坑A[4]處，并且right–憔杨；此時(shí)：left=1鸟赫；right=3；temp=4消别；形成新坑A[1];
3抛蚤、開(kāi)始從右往左，尋找第二個(gè)比temp小的數(shù)妖啥，準(zhǔn)備填充到A[1]的位置上。
當(dāng)right=2時(shí)滿足情況对碌，于是將A[2] 挖走荆虱，填充到上一個(gè)坑A[1]處，并且left++朽们；此時(shí)：left=2怀读；right=2；temp=4骑脱；形成新坑A[2]菜枷。
4、此時(shí)left=right叁丧，則第一趟排序結(jié)束啤誊，將temp填充到中樞點(diǎn)index=2的位置上岳瞭，可以看到，4的左邊都比4小蚊锹，右邊都比4大瞳筏。
5、得到新的中樞點(diǎn)后牡昆，遞歸對(duì)左邊和右邊重復(fù)上述過(guò)程即可完成整個(gè)排序姚炕。
對(duì)挖坑填數(shù)進(jìn)行總結(jié)（引用自上述參考文章）：
1．i =L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]。
2．j–由后向前找比它小的數(shù)丢烘，找到后挖出此數(shù)填前一個(gè)坑a[i]中柱宦。
3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個(gè)坑a[j]中播瞳。
4．再重復(fù)執(zhí)行2掸刊，3二步，直到i==j狐史，將基準(zhǔn)數(shù)填入a[i]中痒给。
算法實(shí)現(xiàn)（java）：
public static void sort(int[] A,int l,int r){ int left=l; int right=r; // index為下標(biāo)，temp用來(lái)保存中樞位置的值骏全，無(wú)關(guān)數(shù)組A,只是一個(gè)臨時(shí)變量而已
測(cè)試程序：
public static void main(String[] arg){ // TODO Auto-generated method stub
打印內(nèi)容如下：
耗時(shí)：9659
