快速排序（Quick Sort）
看到名字，就知道這種排序算法速度非常快。那到底有多快呢？在前面冒泡排序時(shí)，就有提到過這種排序算法，它的平均時(shí)間復(fù)雜度為O(nlogn)，但看到其最壞時(shí)間復(fù)雜度為O(n^2)，不過，雖然有最壞的情況，但是還是有辦法降低最壞情況出現(xiàn)的概率，所以總體來講，效率還是非常高的。但是在前面也介紹過，堆排序與歸并排序，其時(shí)間復(fù)雜度都是O(nlogn)級(jí)別的，但是這三個(gè)O(nlogn)級(jí)別的排序算法，哪個(gè)算法會(huì)更快呢？其實(shí)快速排序會(huì)更加快，也就是說，在本章節(jié)介紹的快速排序會(huì)比對(duì)排序與歸并排序速度更快。
快速排序簡(jiǎn)介
快速排序是1960年由查爾斯·安東尼·理查德·霍爾(Charles Antony Richard Hoare)，一般稱為東尼·霍爾（Tony Hoare）
其實(shí)結(jié)合前面的歸并排序介紹，可以發(fā)現(xiàn)一個(gè)特點(diǎn)，現(xiàn)在的排序算法都是幾十年前的結(jié)論，也就是說，幾十年過去了，到現(xiàn)在還沒有一個(gè)穩(wěn)定的，被大家公認(rèn)的排序算法來替代這些優(yōu)秀的算法，還望大家來突破這些算法。
快速排序執(zhí)行流程
-
從序列中選擇一個(gè)軸點(diǎn)元素（pivot）
-
假設(shè)每次選擇0位置的元素為軸點(diǎn)元素，例如下圖的序列
現(xiàn)在選擇0位置的元素6作為軸點(diǎn)元素，一旦定義好了軸點(diǎn)元素后，就開始執(zhí)行步驟2
-
-
利用軸點(diǎn)元素將序列分割成2個(gè)子序列
- 將小于軸點(diǎn)元素的元素放在軸點(diǎn)元素的前面（左側(cè)）
- 將大于軸點(diǎn)元素的元素放在軸點(diǎn)元素的后面（右側(cè)）
- 等于軸點(diǎn)元素的元素放任意一邊都可以
所以利用上圖的序列，進(jìn)行分割以后，就會(huì)變?yōu)橄聢D的這樣一個(gè)序列，通過這樣分割，相對(duì)于原來的序列，會(huì)變得更加有序一點(diǎn)
-
對(duì)子序列進(jìn)行1,2操作
- 知道不能再分割（子序列中只剩下一個(gè)元素）
所以對(duì)上面的序列再次執(zhí)行1,2操作的話，最終得到的結(jié)果如下圖
再次執(zhí)行1,2操作，得到下圖的結(jié)果
最終，將所有元素一次排好序。
所以可以發(fā)現(xiàn)，快速排序的本質(zhì)是
逐漸將每一個(gè)元素都轉(zhuǎn)換成軸點(diǎn)元素，當(dāng)所有元素都變?yōu)檩S點(diǎn)元素時(shí)，就拍好序了
那這個(gè)流程應(yīng)該怎樣去實(shí)現(xiàn)呢？
構(gòu)造軸點(diǎn)
假設(shè)現(xiàn)在有下列的序列，這個(gè)序列有點(diǎn)特殊，其中有兩個(gè)6，兩個(gè)8，為了表示區(qū)分，方別用6a/6b，8a/8b來表示，其中begin指向首元素，end指向末尾元素（這里的end和前面章節(jié)的end指向的位置有一點(diǎn)區(qū)別）
現(xiàn)在希望將6a變?yōu)檩S點(diǎn)，一般會(huì)先將該元素進(jìn)行備份，利用一個(gè)臨時(shí)的變量，將該值保存起來。
由于現(xiàn)在是begin有空的位置，所以從end到begin+1開始掃描元素，在本序列中，首先掃描到的是7，由于7大于軸點(diǎn)元素，所以只需要將end--即可，繼續(xù)掃描
現(xiàn)在掃描到的是5，由于5是小于軸點(diǎn)元素，所以應(yīng)該放到序列的左邊。然后begin++
現(xiàn)在空的位置變?yōu)閑nd方向，所以掃描的防線變?yōu)閺腷egin到end的方向。掃描到的第一個(gè)元素是8a，由于8a是比軸點(diǎn)元素大的，所以將8a的值直接覆蓋end指向的位置，然后將end--
由于現(xiàn)在空位置是由begin直接指向的，所以本次掃描方向由end方向到begin方向，繼續(xù)掃描，這次掃描發(fā)現(xiàn)元素為9，比軸點(diǎn)元素大，所以只需要將end--即可
由于空位置沒有發(fā)生變化，所以繼續(xù)從end掃描到begin，本次掃描到的元素為4，其值比軸點(diǎn)元素小，所以將元素4直接覆蓋掉begin指向的位置，然后begin++
現(xiàn)在空位置是右end指針指向，所以掃描方向發(fā)生變化，變?yōu)閺腷egin掃描到end，由于本次掃描到的元素為8b，值比軸點(diǎn)元素大，所以將8b的值覆蓋掉end指針指向的位置，然后進(jìn)行end--操作
完成后，空的位置現(xiàn)在有begin指針指向，所以掃描方向變?yōu)閑nd到begin方向，本次掃描到的元素是6b，是等于軸點(diǎn)元素的，由于等于軸點(diǎn)元素的元素，放軸點(diǎn)元素任意一邊都可以，所以直接end--就行，不過這里執(zhí)行的操作是將相等的元素放到另外一邊，所以這里是將end蚊子相等的元素放在begin，begin++，最終的效果如下圖
現(xiàn)在空的位置由end指向，所以掃描方向由begin到end方向。不過這次掃描發(fā)現(xiàn)值比軸點(diǎn)元素小，所以直接begin++就可以了，begin++后得到的begin等于end，一旦發(fā)現(xiàn)begin和end重疊，就意味著軸點(diǎn)元素構(gòu)建完畢
由于之前備份了6a的值，所以現(xiàn)在要做的事情是將6a的值，覆蓋當(dāng)前空出來的位置，這樣6a就歸位了
所以最終發(fā)現(xiàn)，6a變?yōu)檩S點(diǎn)后，最終找到了自己的位置，并且軸點(diǎn)構(gòu)建完畢。
軸點(diǎn)構(gòu)建總結(jié)：掃描方向主要看空出來的位置是由begin指向還是有end指向
- 如果end指向空出來的元素， 則從begin掃描到end
- 如果是begin指向空出來的元素，則從end掃描到begin
根據(jù)上面的分析，最終可以得到獲取軸點(diǎn)的實(shí)現(xiàn)代碼如下
/*
* 構(gòu)造出[begin,end)范圍內(nèi)的軸點(diǎn)元素
* @return 軸點(diǎn)元素的最終位置
* */
private int pivotIndex(int begin, int end) {
//備份軸點(diǎn)元素
E pivot = array[begin];
//end指向最后一個(gè)元素
end--;
while (begin < end) {
while (begin < end) {
if (cmp(pivot,array[end]) < 0) {//右邊元素大于軸點(diǎn)元素
end--;
} else {//右邊元素小于等于軸點(diǎn)元素
array[begin++] = array[end];
break;
}
}
while (begin < end) {
if (cmp(pivot,array[begin]) >0) {//左邊元素小于軸點(diǎn)
begin++;
} else {//左邊元素大于等于軸點(diǎn)元素
array[end--] = array[begin];
break;
}
}
}
//將軸點(diǎn)元素放入最終的位置
array[begin] = pivot;
//返回軸點(diǎn)元素的位置
return begin;
}
然后利用獲取到的軸點(diǎn)，對(duì)begin到end范圍內(nèi)的元素進(jìn)行快速排序的代碼
/*
* 對(duì)[begin,end)范圍內(nèi)的元素進(jìn)行快速排序
* */
private void quickSort(int begin, int end) {
if (end - begin < 2) return;
//確定軸點(diǎn)位置
int mid = pivotIndex(begin,end);
//對(duì)子序列也進(jìn)行快速排序
quickSort(begin,mid);//左邊子序列快速排序
quickSort(mid + 1 ,end);//右邊子序列快速排序
}
利用上面代碼，結(jié)合前面的幾種排序算法，對(duì)20000條數(shù)據(jù)進(jìn)行排序的結(jié)果如下圖
可以看到，快速排序與前面幾種排序結(jié)果排序后，得到的結(jié)果非常優(yōu)秀。如果再將數(shù)據(jù)進(jìn)行增加到50000條數(shù)據(jù)，得到的結(jié)果就更加明顯了，結(jié)果如下（這里的排序，對(duì)前面性能較差的幾種排序就不再做對(duì)比了）
時(shí)間復(fù)雜度分析
在軸點(diǎn)左右元素?cái)?shù)量比較均勻的情況下，是快速排序性能最佳的時(shí)候。
在這個(gè)時(shí)候，可以得到所消耗時(shí)間的表達(dá)式為：T(n) = 2 * T(n/2) + O(n)
可以看到，這個(gè)表達(dá)式與歸并排序的表達(dá)式是一樣的，所以在最好的情況下， 快速排序的時(shí)間復(fù)雜度與歸并排序的時(shí)間復(fù)雜度相同，都是O(nlogn)
如果軸點(diǎn)左右兩邊元素?cái)?shù)量及其不均勻，則是時(shí)間復(fù)雜度最壞的情況。
例如現(xiàn)在有如下的序列
將元素7作為軸點(diǎn)，軸點(diǎn)構(gòu)造完成后的結(jié)果為
并往復(fù)執(zhí)行構(gòu)造軸點(diǎn)，最終得到的每一步結(jié)果為
所以在這個(gè)時(shí)候，就是最壞時(shí)間復(fù)雜度的時(shí)候。在這種情況下，所消耗時(shí)間的表達(dá)式為：T(n) = T(n-1) + O(n) = O(n^2)；
避免最壞情況
為了降低最壞情況的出現(xiàn)概率，一般采取的做法是
- 隨機(jī)選擇軸點(diǎn)元素
所以優(yōu)化后的代碼為
private int pivotIndex(int begin, int end) {
//隨機(jī)選擇一個(gè)元素跟begin位置進(jìn)行交換
swap(begin,(int)(Math.random() * (end - begin)) + begin);
//備份軸點(diǎn)元素
E pivot = array[begin];
//end指向最后一個(gè)元素
end--;
while (begin < end) {
while (begin < end) {
if (cmp(pivot,array[end]) < 0) {//右邊元素大于軸點(diǎn)元素
end--;
} else {//右邊元素小于等于軸點(diǎn)元素
array[begin++] = array[end];
break;
}
}
while (begin < end) {
if (cmp(pivot,array[begin]) >0) {//左邊元素小于軸點(diǎn)
begin++;
} else {//左邊元素大于等于軸點(diǎn)元素
array[end--] = array[begin];
break;
}
}
}
//將軸點(diǎn)元素放入最終的位置
array[begin] = pivot;
//返回軸點(diǎn)元素的位置
return begin;
}
快速排序時(shí)間復(fù)雜度總結(jié)：
最好，平均時(shí)間復(fù)雜度為：O(nlogn)
最壞時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(logn)
與軸點(diǎn)相等的元素
在前面，如果遇到軸點(diǎn)元素相等的元素，都是直接將該元素放到軸點(diǎn)元素的另一邊。具體是怎么做的呢？請(qǐng)看下圖，現(xiàn)在所有元素都是相等的
-
備份軸點(diǎn)元素
-
執(zhí)行第一次確定元素位置，發(fā)現(xiàn)值是相等的，這時(shí)，原來軸點(diǎn)右邊的元素，被放到了軸點(diǎn)的左邊
-
執(zhí)行第二次確定元素位置，發(fā)現(xiàn)值是相等的，這時(shí)，將原來軸點(diǎn)左邊的元素，被放到軸點(diǎn)的右邊
-
執(zhí)行第三次確定元素位置,發(fā)現(xiàn)值是相等的，這時(shí)，原來軸點(diǎn)右邊的元素，被放到了軸點(diǎn)的左邊
-
執(zhí)行第四次確定元素位置，發(fā)現(xiàn)值是相等的，這時(shí)，將原來軸點(diǎn)左邊的元素，被放到軸點(diǎn)的右邊
-
將備份的元素放到begin與end重合的位置
發(fā)現(xiàn)，如果用原來的這種確定軸點(diǎn)的方式，有一個(gè)好處就是，軸點(diǎn)確定以后，依然可以平均分割原來的序列。
所以在pivot與end元素進(jìn)行比較時(shí)，不是≤或者≥的原因是為了提高性能，避免出現(xiàn)最壞時(shí)間復(fù)雜度的情況。
如果將cmp位置的判斷分別改為≤，≥會(huì)起到什么效果呢？
這樣進(jìn)行判斷，會(huì)導(dǎo)致軸點(diǎn)元素切割出來的序列，非常不均勻，可能會(huì)導(dǎo)致最壞時(shí)間復(fù)雜度O(n^2)
為了進(jìn)行對(duì)比，現(xiàn)生成5萬條相等的數(shù)據(jù)，利用原來的算法進(jìn)行測(cè)試，得到的結(jié)果如下圖
現(xiàn)在將判斷條件分別改為≤，≥，得到的結(jié)果如下圖
最終控制臺(tái)打印出了非常多的這種信息，從提示信息可以看出，是發(fā)生了棧溢出，也就是說?？臻g消耗完了，原因是現(xiàn)在的軸點(diǎn)切割非常不均勻，每次切割只會(huì)減少一個(gè)數(shù)據(jù)規(guī)模，也就意味著quickSort函數(shù)會(huì)遞歸調(diào)用n次，在當(dāng)前程序中，是要遞歸調(diào)用5萬次，需要開辟5萬次?？臻g，最終導(dǎo)致?？臻g不夠用。
所以為了對(duì)比出最終的效果，現(xiàn)在將數(shù)據(jù)規(guī)模調(diào)整到1萬條。在不加＝的情況下，得到的結(jié)果為
加上＝后的結(jié)果為
可以看到，最終的比較結(jié)果，差距非常大。所以在進(jìn)行比較判斷的時(shí)候，不要使用≥或者≤
完！
