算法的精髓在于，跟它一比高數(shù)也顯得那么生動活潑…嘀掸。本文由啊哈磊吐槽而成紫岩，話說我還是頭一次見到這么萌的變量，簡直顛覆我對變量這個兵種睬塌、對算法這個種族的傳統(tǒng)觀念泉蝌。正在被算法欺負(fù)嗎歇万？快進(jìn)來看看：
高快省的排序算法
有沒有既不浪費空間又可以快一點的排序算法呢？那就是“快速排序”啦勋陪！光聽這個名字是不是就覺得很高端呢贪磺。
假設(shè)我們現(xiàn)在對“6 1 2 7 9 3 4 5 10 8”這個10個數(shù)進(jìn)行排序。首先在這個序列中隨便找一個數(shù)作為基準(zhǔn)數(shù)（不要被這個名詞嚇到了诅愚，就是一個用來參照的數(shù)寒锚，待會你就知道它用來做啥的了）。為了方便违孝，就讓第一個數(shù)6作為基準(zhǔn)數(shù)吧刹前。接下來，需要將這個序列中所有比基準(zhǔn)數(shù)大的數(shù)放在6的右邊雌桑，比基準(zhǔn)數(shù)小的數(shù)放在6的左邊喇喉，類似下面這種排列：
3 1 2 5 4 6 9 7 10 8
在初始狀態(tài)下，數(shù)字6在序列的第1位校坑。我們的目標(biāo)是將6挪到序列中間的某個位置拣技，假設(shè)這個位置是k。現(xiàn)在就需要尋找這個k耍目，并且以第k位為分界點膏斤，左邊的數(shù)都小于等于6，右邊的數(shù)都大于等于6邪驮。想一想掸绞，你有辦法可以做到這點嗎？
排序算法顯神威
方法其實很簡單：分別從初始序列“6 1 2 7 9 3 4 5 10 8”兩端開始“探測”耕捞。先從右往左找一個小于6的數(shù)衔掸，再從左往右找一個大于6的數(shù)，然后交換他們俺抽。這里可以用兩個變量i和j敞映，分別指向序列最左邊和最右邊。我們?yōu)檫@兩個變量起個好聽的名字“哨兵i”和“哨兵j”磷斧。剛開始的時候讓哨兵i指向序列的最左邊（即i=1）振愿，指向數(shù)字6。讓哨兵j指向序列的最右邊（即=10）弛饭，指向數(shù)字冕末。
首先哨兵j開始出動。因為此處設(shè)置的基準(zhǔn)數(shù)是最左邊的數(shù)侣颂，所以需要讓哨兵j先出動档桃，這一點非常重要（請自己想一想為什么）。哨兵j一步一步地向左挪動（即j--）憔晒，直到找到一個小于6的數(shù)停下來藻肄。接下來哨兵i再一步一步向右挪動（即i++）蔑舞，直到找到一個數(shù)大于6的數(shù)停下來。最后哨兵j停在了數(shù)字5面前嘹屯，哨兵i停在了數(shù)字7面前攻询。
現(xiàn)在交換哨兵i和哨兵j所指向的元素的值。交換之后的序列如下：
6 1 2 5 9 3 4 7 10 8
到此州弟，第一次交換結(jié)束柴梆。接下來開始哨兵j繼續(xù)向左挪動（再友情提醒诈豌，每次必須是哨兵j先出發(fā)）丙曙。他發(fā)現(xiàn)了4（比基準(zhǔn)數(shù)6要小鹊漠，滿足要求）之后停了下來。哨兵i也繼續(xù)向右挪動的浙滤，他發(fā)現(xiàn)了9（比基準(zhǔn)數(shù)6要大，滿足要求）之后停了下來气堕。此時再次進(jìn)行交換纺腊，交換之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交換結(jié)束，“探測”繼續(xù)茎芭。哨兵j繼續(xù)向左挪動揖膜，他發(fā)現(xiàn)了3（比基準(zhǔn)數(shù)6要小，滿足要求）之后又停了下來梅桩。哨兵i繼續(xù)向右移動壹粟，糟啦！此時哨兵i和哨兵j相遇了宿百，哨兵i和哨兵j都走到3面前趁仙。說明此時“探測”結(jié)束。我們將基準(zhǔn)數(shù)6和3進(jìn)行交換垦页。交換之后的序列如下：
3 1 2 5 4 6 9 7 10 8
到此第一輪“探測”真正結(jié)束雀费。此時以基準(zhǔn)數(shù)6為分界點，6左邊的數(shù)都小于等于6痊焊，6右邊的數(shù)都大于等于6盏袄。回顧一下剛才的過程薄啥，其實哨兵j的使命就是要找小于基準(zhǔn)數(shù)的數(shù)辕羽，而哨兵i的使命就是要找大于基準(zhǔn)數(shù)的數(shù)，直到i和j碰頭為止垄惧。
OK刁愿，解釋完畢。現(xiàn)在基準(zhǔn)數(shù)6已經(jīng)歸位到逊，它正好處在序列的第6位酌毡。此時我們已經(jīng)將原來的序列克握，以6為分界點拆分成了兩個序列，左邊的序列是“3 1 2 5 4”枷踏，右邊的序列是“9 7 10 8”菩暗。接下來還需要分別處理這兩個序列。因為6左邊和右邊的序列目前都還是很混亂的旭蠕。不過不要緊停团，我們已經(jīng)掌握了方法，接下來只要模擬剛才的方法分別處理6左邊和右邊的序列即可√桶荆現(xiàn)在先來處理6左邊的序列現(xiàn)吧佑稠。
左邊的序列是“3 1 2 5 4”。請將這個序列以3為基準(zhǔn)數(shù)進(jìn)行調(diào)整旗芬，使得3左邊的數(shù)都小于等于3舌胶，3右邊的數(shù)都大于等于3。好了開始動筆吧
如果你模擬的沒有錯疮丛，調(diào)整完畢之后的序列的順序應(yīng)該是：
2 1 3 5 4
OK幔嫂，現(xiàn)在3已經(jīng)歸位。接下來需要處理3左邊的序列“2 1”和右邊的序列“5 4”誊薄。對序列“2 1”以2為基準(zhǔn)數(shù)進(jìn)行調(diào)整履恩，處理完畢之后的序列為“1 2”，到此2已經(jīng)歸位呢蔫。序列“1”只有一個數(shù)切心，也不需要進(jìn)行任何處理。至此我們對序列“2 1”已全部處理完畢片吊，得到序列是“1 2”绽昏。序列“5 4”的處理也仿照此方法，最后得到的序列如下：
1 2 3 4 5 6 9 7 10 8
對于序列“9 7 10 8”也模擬剛才的過程俏脊，直到不可拆分出新的子序列為止而涉。最終將會得到這樣的序列，如下
1 2 3 4 5 6 7 8 9 10
到此联予，排序完全結(jié)束啼县。細(xì)心的同學(xué)可能已經(jīng)發(fā)現(xiàn)，快速排序的每一輪處理其實就是將這一輪的基準(zhǔn)數(shù)歸位沸久，直到所有的數(shù)都?xì)w位為止季眷，排序就結(jié)束了。下面上個霸氣的圖來描述下整個算法的處理過程卷胯。
這是為什么呢子刮？快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的挺峡。每次排序的時候設(shè)置一個基準(zhǔn)點葵孤，將小于等于基準(zhǔn)點的數(shù)全部放到基準(zhǔn)點的左邊，將大于等于基準(zhǔn)點的數(shù)全部放到基準(zhǔn)點的右邊橱赠。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換尤仍，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了狭姨，速度自然就提高了宰啦。當(dāng)然在最壞的情況下，仍可能是相鄰的兩個數(shù)進(jìn)行了交換饼拍。因此快速排序的最差時間復(fù)雜度和冒泡排序是一樣的都是O(N2)赡模，它的平均時間復(fù)雜度為O(NlogN)。其實快速排序是基于一種叫做“二分”的思想师抄。我們后面還會遇到“二分”思想漓柑，到時候再聊。先上代碼叨吮，如下：
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
if (leftIndex >= rightIndex) {//如果數(shù)組長度為0或1時返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//記錄比較基準(zhǔn)數(shù)
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先從右邊j開始查找比基準(zhǔn)數(shù)小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基準(zhǔn)數(shù)大辆布，繼續(xù)查找
j--;
}
//如果比基準(zhǔn)數(shù)小，則將查找到的小值調(diào)換到i的位置
array[i] = array[j];
/**** 當(dāng)在右邊查找到一個比基準(zhǔn)數(shù)小的值時挤安，就從i開始往后找比基準(zhǔn)數(shù)大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基準(zhǔn)數(shù)小谚殊，繼續(xù)查找
i++;
}
//如果比基準(zhǔn)數(shù)大丧鸯，則將查找到的大值調(diào)換到j(luò)的位置
array[j] = array[i];
}
//將基準(zhǔn)數(shù)放到正確位置
array[i] = @(key);
/**** 遞歸排序 ***/
//排序基準(zhǔn)數(shù)左邊的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基準(zhǔn)數(shù)右邊的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
可以輸入以下數(shù)據(jù)進(jìn)行驗證
1061279345108
運行結(jié)果是
12345678910
漲姿勢環(huán)節(jié)
快速排序由 C. A. R. Hoare（東尼霍爾蛤铜，Charles Antony Richard Hoare）在1960年提出，之后又有許多人做了進(jìn)一步的優(yōu)化丛肢。如果你對快速排序感興趣可以去看看東尼霍爾1962年在Computer Journal發(fā)表的論文“Quicksort”以及《算法導(dǎo)論》的第七章围肥。快速排序算法僅僅是東尼霍爾在計算機(jī)領(lǐng)域才能的第一次顯露蜂怎，后來他受到了老板的賞識和重用穆刻，公司希望他為新機(jī)器設(shè)計一個新的高級語言。你要知道當(dāng)時還沒有PASCAL或者C語言這些高級的東東杠步。后來東尼霍爾參加了由Edsger Wybe Dijkstra（1972年圖靈獎得主氢伟，這個大神我們后面還會遇到的到時候再細(xì)聊）舉辦的“ALGOL 60”培訓(xùn)班，他覺得自己與其沒有把握去設(shè)計一個新的語言幽歼，還不如對現(xiàn)有的“ALGOL 60”進(jìn)行改進(jìn)朵锣，使之能在公司的新機(jī)器上使用。于是他便設(shè)計了“ALGOL 60”的一個子集版本甸私。這個版本在執(zhí)行效率和可靠性上都在當(dāng)時“ALGOL 60”的各種版本中首屈一指诚些，因此東尼霍爾受到了國際學(xué)術(shù)界的重視。后來他在“ALGOL X”的設(shè)計中還發(fā)明了大家熟知的“case”語句皇型，后來也被各種高級語言廣泛采用诬烹，比如PASCAL砸烦、C、Java語言等等绞吁。當(dāng)然幢痘，東尼霍爾在計算機(jī)領(lǐng)域的貢獻(xiàn)還有很多很多，他在1980年獲得了圖靈獎掀泳。
