http://data.biancheng.net/view/117.html
快速排序算法詳解（原理疚膊、實(shí)現(xiàn)和時(shí)間復(fù)雜度）
快速排序是對(duì)冒泡排序的一種改進(jìn)，由 C.A.R.Hoare（Charles Antony Richard Hoare让簿，東尼·霍爾）在 1962 年提出。
快速排序的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分豆挽，其中一部分的所有數(shù)據(jù)比另一部分的所有數(shù)據(jù)要小差牛，再按這種方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序音羞，整個(gè)排序過程可以遞歸進(jìn)行景描，使整個(gè)數(shù)據(jù)變成有序序列。
快速排序的原理
排序算法的思想非常簡(jiǎn)單秀撇，在待排序的數(shù)列中超棺，我們首先要找一個(gè)數(shù)字作為基準(zhǔn)數(shù)（這只是個(gè)專用名詞）。為了方便呵燕，我們一般選擇第 1 個(gè)數(shù)字作為基準(zhǔn)數(shù)（其實(shí)選擇第幾個(gè)并沒有關(guān)系）棠绘。接下來(lái)我們需要把這個(gè)待排序的數(shù)列中小于基準(zhǔn)數(shù)的元素移動(dòng)到待排序的數(shù)列的左邊，把大于基準(zhǔn)數(shù)的元素移動(dòng)到待排序的數(shù)列的右邊再扭。這時(shí)氧苍，左右兩個(gè)分區(qū)的元素就相對(duì)有序了；接著把兩個(gè)分區(qū)的元素分別按照上面兩種方法繼續(xù)對(duì)每個(gè)分區(qū)找出基準(zhǔn)數(shù)泛范，然后移動(dòng)让虐，直到各個(gè)分區(qū)只有一個(gè)數(shù)時(shí)為止。
這是典型的分治思想罢荡，即分治法赡突。下面我們對(duì)一個(gè)實(shí)際例子進(jìn)行算法描述，講解快速排序的排序步驟区赵。
以 47惭缰、29、71笼才、99漱受、78、19患整、24拜效、47 的待排序的數(shù)列為例進(jìn)行排序，為了方便區(qū)分兩個(gè) 47各谚，我們對(duì)后面的 47 增加一個(gè)下畫線，即待排序的數(shù)列為 47到千、29昌渤、71、99憔四、78膀息、19、24了赵、47潜支。
首先我們需要在數(shù)列中選擇一個(gè)基準(zhǔn)數(shù)，我們一般會(huì)選擇中間的一個(gè)數(shù)或者頭尾的數(shù)柿汛，這里直接選擇第 1 個(gè)數(shù) 47 作為基準(zhǔn)數(shù)冗酿，接著把比 47 小的數(shù)字移動(dòng)到左邊，把比 47 大的數(shù)字移動(dòng)到右邊，對(duì)于相等的數(shù)字不做移動(dòng)裁替。所以實(shí)際上我們需要找到中間的某個(gè)位置 k项玛，這樣 k 左邊的值全部比 k 上的值小，k 右邊的值全部比 k 上的值大弱判。
接下來(lái)開始移動(dòng)元素襟沮。怎么移動(dòng)呢？其實(shí)冒泡排序也涉及對(duì)元素的移動(dòng)昌腰，但是那樣移動(dòng)起來(lái)很累开伏，比如把最后一個(gè)元素移動(dòng)到第 1 個(gè)，就需要比較 n-1 次遭商，同時(shí)交換 n-1 次固灵，效率很低。其實(shí)株婴，只需把第 1 個(gè)元素和最后一個(gè)元素交換就好了怎虫，這種思想是不是在排序時(shí)可以借鑒呢？之前說快速排序就是對(duì)冒泡排序的一個(gè)改進(jìn)困介，就是這個(gè)原因大审。
快速排序的操作是這樣的：首先從數(shù)列的右邊開始往左邊找，我們?cè)O(shè)這個(gè)下標(biāo)為 i座哩，也就是進(jìn)行減減操作（i--）徒扶，找到第 1 個(gè)比基準(zhǔn)數(shù)小的值，讓它與基準(zhǔn)值交換根穷；接著從左邊開始往右邊找姜骡，設(shè)這個(gè)下標(biāo)為 j，然后執(zhí)行加加操作（j++）屿良，找到第 1 個(gè)比基準(zhǔn)數(shù)大的值圈澈，讓它與基準(zhǔn)值交換；然后繼續(xù)尋找尘惧，直到 i 與 j 相遇時(shí)結(jié)束康栈，最后基準(zhǔn)值所在的位置即 k 的位置，也就是說 k 左邊的值均比 k 上的值小喷橙，而 k 右邊的值都比 k 上的值大啥么。
所以對(duì)于上面的數(shù)列 47、29贰逾、71悬荣、99、78疙剑、19氯迂、24践叠、47，進(jìn)行第 1 趟第 1 個(gè)交換的排序情況如下囚戚，第 1 次的操作情況如圖?1 所示酵熙。
圖 1 第 1 次發(fā)現(xiàn)可以交換的數(shù)
交換之后，j 移動(dòng)到了下標(biāo)為 6 的位置驰坊，對(duì) i 繼續(xù)掃描匾二，如圖 2 所示。
圖 2 第 2 次發(fā)現(xiàn)可交換的值
此時(shí)交換后的數(shù)列變?yōu)?24拳芙、29察藐、47、99舟扎、78分飞、19、71睹限、47譬猫。接下來(lái)我們繼續(xù)對(duì) i、j 進(jìn)行操作羡疗，如圖 3 所示染服，繼續(xù)進(jìn)行 i-- 及 j++ 的比較操作。
圖 3 繼續(xù)進(jìn)行 i 與 j 的移動(dòng)
進(jìn)行了這兩次 i叨恨、j 的移動(dòng)柳刮、比較、交換之后痒钝，我們最終得到的數(shù)列是 24秉颗、29、19送矩、47蚕甥、78、99栋荸、71梢灭、47。接下來(lái)我們繼續(xù)進(jìn)行 i-- 的操作蒸其，發(fā)現(xiàn)在 i 為 4 時(shí)比 47 大不用交換，在 i 為 3 時(shí)與 j 相遇库快，這時(shí)就不需要繼續(xù)移動(dòng)摸袁、比較了，已經(jīng)找到 k 了义屏，并且 k 的值為 3靠汁。我們可以確認(rèn)一下當(dāng)前的數(shù)列是不是 k 左邊的值都比 47 小蜂大，而 k 右邊的值都比 47 大（由于要保持相對(duì)位置不變，所以 47 同樣在基準(zhǔn)值 47 的右邊）蝶怔。
47 這個(gè)值已經(jīng)落到了它該在的位置奶浦，第 1 趟排序完成了。接下來(lái)就是以 k 為基準(zhǔn)踢星，分為兩部分澳叉，然后在左右兩部分分別執(zhí)行上述排序操作，最后數(shù)據(jù)會(huì)分為 4 部分沐悦；接著對(duì)每部分進(jìn)行操作成洗，直到每部分都只有一個(gè)值為止。
接下來(lái)進(jìn)行第 2 趟排序藏否，現(xiàn)在左邊部分為 24瓶殃、29、19副签，我們選擇第 1 個(gè)數(shù) 24 作為基準(zhǔn)數(shù)遥椿，接著進(jìn)行 i--、j++ 的操作淆储，我們發(fā)現(xiàn) i 最初的值為 19冠场，比 24 這個(gè)基準(zhǔn)值小，所以與基準(zhǔn)值進(jìn)行交換遏考，得到的數(shù)列為 19慈鸠、29、24灌具；當(dāng) j 為 1 時(shí)青团，我們發(fā)現(xiàn) 29 比 24 大，所以與基準(zhǔn)值進(jìn)行交換咖楣，得到的數(shù)列 19督笆、24、29诱贿，此時(shí) i 為 2娃肿，j 為 1；繼續(xù) i-- 時(shí)發(fā)現(xiàn) i 為 1珠十，與 j 相遇料扰，左邊部分的數(shù)列的 k 為 1，并且左右兩部分分別只有一個(gè)元素焙蹭，此時(shí)第 2 輪排序的左邊部分的排序結(jié)束晒杈，同時(shí)左邊部分的所有數(shù)據(jù)都排序完成。
我們接著看右邊部分的排序孔厉，待排序的數(shù)列為 78拯钻、99帖努、71、47粪般，我們同樣選擇第 1 個(gè)值 78 為基準(zhǔn)值拼余，接下來(lái)進(jìn)行 i 與 j 的移動(dòng)與比較，發(fā)現(xiàn)47?比 78 小亩歹，進(jìn)行交換匙监，得到的數(shù)列 47、99捆憎、71舅柜、78；從左往右發(fā)現(xiàn) 99 比基準(zhǔn)值 78 大躲惰，進(jìn)行交換致份，得到的數(shù)列為47、78础拨、71氮块、99；繼續(xù)從右向左看诡宗，發(fā)現(xiàn) 71 比基準(zhǔn)值 78 小滔蝉，進(jìn)行交換，得到的數(shù)列為?47塔沃、71蝠引、78、99蛀柴。此時(shí) i 在整體數(shù)組中的下標(biāo)為 6螃概，j 為 5，若繼續(xù) j++ 則與 i 相遇鸽疾，所以完成此輪排序吊洼。
此時(shí)右邊數(shù)列的 k 為 6，一般會(huì)是相遇的位置制肮，也就是基準(zhǔn)值所在的位置冒窍，這時(shí)數(shù)列又被分為兩部分，左邊是47豺鼻、71综液，右邊是 99，需要繼續(xù)對(duì)左邊部分的數(shù)據(jù)進(jìn)行排序儒飒，雖然只有兩個(gè)數(shù)據(jù)意乓，但我們還是繼續(xù)按照快速排序的思想操作一下，選擇?47?作為基準(zhǔn)數(shù)，將i進(jìn)行從右向左的移動(dòng)届良、比較，發(fā)現(xiàn) i 與 j 相等時(shí)沒有產(chǎn)生移動(dòng)圣猎，完成第 2 輪排序士葫。
至此，所有排序都已經(jīng)完成送悔，最終數(shù)列的結(jié)果是 19慢显、24、29欠啤、47荚藻、47、71洁段、78应狱、99，怎么樣祠丝，快速排序是不是非常簡(jiǎn)單地完成了所有的排序呢疾呻？雖然本次快速排序沒有改變相同值的元素的順序，但是由于快速排序需要對(duì)數(shù)列中的元素來(lái)回移動(dòng)写半，有時(shí)還是會(huì)改變相對(duì)順序的（比如 47 在第 1 輪的移動(dòng)過程中就被移動(dòng)到?47?的右邊了）岸蜗，所以快速排序并不是一個(gè)穩(wěn)定的算法。
快速排序的實(shí)現(xiàn)
通過以上的學(xué)習(xí)叠蝇，你是否可以自己寫出快速排序的實(shí)現(xiàn)代碼呢璃岳？在接著學(xué)習(xí)之前，最好自己能對(duì)代碼的實(shí)現(xiàn)進(jìn)行一些思考悔捶，然后和下面的內(nèi)容進(jìn)行比對(duì)铃慷，看看自己有哪些疏忽之處。
其實(shí)快速排序有一個(gè)比較簡(jiǎn)單的思想炎功，就是遞歸枚冗。對(duì)于每一趟排序都是一樣的思想，只不過需要進(jìn)行排序的數(shù)組的范圍越來(lái)越小了蛇损，使用遞歸實(shí)現(xiàn)這種排序最適合不過了赁温。
publicclass QuickSort{
privateint[]array;
publicQuickSort(int[]array){
this.array=array;
}
publicvoidsort(){
quickSort(array,0,array.length-1);
}
publicvoidprint(){
for(inti=0;i<array.length;i++){
System.out.println(array[i]);
}
}
/**
? ? * 遞歸排序
? ? * @param src
? ? * @param begin
? ? * @param end
? ? */
privatevoidquickSort(int[]src,intbegin,intend){
if(begin<end){
intkey=src[begin];
inti=begin;
intj=end;
while(i<j){
while(i<j&&src[j]>key){
j--;
}
if(i<j){
src[i]=src[j];
i++;
}
while(i<j&&src[i]<key){
i++;
}
if(i<j){
src[j]=src[i];
j--;
}
}
src[i]=key;
quickSort(src,begin,i-1);
quickSort(src,i+1,end);
}
}
}
下面是測(cè)試代碼，用于驗(yàn)證代碼的正確性淤齐。
publicclass SortTest{
publicstaticvoidmain(String[]args){
testQuickSort();
}
/**
? ? * 快速排序
? ? */
privatestaticvoidtestQuickSort(){
int[]array={5,9,1,9,5,3,7,6,1};
QuickSort quickSort=newQuickSort(array);
quickSort.sort();
quickSort.print();
}
}
快速排序的特點(diǎn)及性能
快速排序是在冒泡排序的基礎(chǔ)上改進(jìn)而來(lái)的股囊，冒泡排序每次只能交換相鄰的兩個(gè)元素，而快速排序是跳躍式的交換更啄，交換的距離很大稚疹，因此總的比較和交換次數(shù)少了很多，速度也快了不少祭务。
但是快速排序在最壞情況下的時(shí)間復(fù)雜度和冒泡排序一樣内狗，是?O(n2)怪嫌，實(shí)際上每次比較都需要交換，但是這種情況并不常見柳沙。我們可以思考一下如果每次比較都需要交換岩灭，那么數(shù)列的平均時(shí)間復(fù)雜度是?O(nlogn)，事實(shí)上在大多數(shù)時(shí)候赂鲤，排序的速度要快于這個(gè)平均時(shí)間復(fù)雜度噪径。這種算法實(shí)際上是一種分治法思想，也就是分而治之数初，把問題分為一個(gè)個(gè)的小部分來(lái)分別解決找爱，再把結(jié)果組合起來(lái)。
快速排序只是使用數(shù)組原本的空間進(jìn)行排序泡孩，所以所占用的空間應(yīng)該是常量級(jí)的车摄，但是由于每次劃分之后是遞歸調(diào)用，所以遞歸調(diào)用在運(yùn)行的過程中會(huì)消耗一定的空間珍德，在一般情況下的空間復(fù)雜度為?O(logn)练般，在最差的情況下，若每次只完成了一個(gè)元素锈候，那么空間復(fù)雜度為?O(n)薄料。所以我們一般認(rèn)為快速排序的空間復(fù)雜度為?O(logn)。
快速排序是一個(gè)不穩(wěn)定的算法泵琳，在經(jīng)過排序之后摄职，可能會(huì)對(duì)相同值的元素的相對(duì)位置造成改變。
快速排序基本上被認(rèn)為是相同數(shù)量級(jí)的所有排序算法中获列，平均性能最好的谷市。
