快速排序（Quicksort）是對冒泡排序的一種改進逛裤。
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分恢暖，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序岸售，整個排序過程可以遞歸進行错敢，以此達到整個數(shù)據(jù)變成有序序列翰灾。
例：
創(chuàng)建變量i=0（指向第一個數(shù)據(jù)）, j=5(指向最后一個數(shù)據(jù)), k=6(賦值為第一個數(shù)據(jù)的值)。
我們要把所有比k小的數(shù)移動到k的左面稚茅，所以我們可以開始尋找比6小的數(shù)预侯，從j開始，從右往左找峰锁，不斷遞減變量j的值萎馅，我們找到第一個下標3的數(shù)據(jù)比6小，于是把數(shù)據(jù)3移到下標0的位置虹蒋，把下標0的數(shù)據(jù)6移到下標3糜芳，完成第一次比較：
此時，i=0 j=3 k=6
接著魄衅，開始第二次比較峭竣，這次要變成找比k大的了，而且要從前往后找了晃虫。遞加變量i皆撩，發(fā)現(xiàn)下標2的數(shù)據(jù)是第一個比k大的，于是用下標2的數(shù)據(jù)7和j指向的下標3的數(shù)據(jù)的6做交換哲银，數(shù)據(jù)狀態(tài)變成下表：
此時扛吞，i=2 j=3 k=6
稱上面兩次比較為一個循環(huán)。
接著荆责，再遞減變量j滥比，不斷重復進行上面的循環(huán)比較。
在本例中做院，我們進行一次循環(huán)盲泛，就發(fā)現(xiàn)i和j“碰頭”了：他們都指向了下標2濒持。于是，第一遍比較結束寺滚。得到結果如下柑营，凡是k(=6)左邊的數(shù)都比它小，凡是k右邊的數(shù)都比它大：
如果i和j沒有碰頭的話村视，就遞加i找大的由境，還沒有，就再遞減j找小的蓖议，如此反復，不斷循環(huán)讥蟆。注意判斷和尋找是同時進行的勒虾。
然后，對k兩邊的數(shù)據(jù)瘸彤，再分組分別進行上述的過程修然，直到不能再分組為止。
注意：第一遍快速排序不會直接得到最終結果质况，只會把比k大和比k小的數(shù)分到k的兩邊愕宋。為了得到最后結果，需要再次對下標2兩邊的數(shù)組分別執(zhí)行此步驟结榄，然后再分解數(shù)組中贝，直到數(shù)組不能再分解為止（只有一個數(shù)據(jù)），才能得到正確結果臼朗。
- (void)quickSort:(NSMutableArray *)arrSort leftIndex:(int)left rightIndex:(int)right{
if (left >= right) {
return;
}
int i = left;
int j = right;
int k = [arrSort[left] intValue]; // 用來對比的基數(shù)
while (i < j) {
// k >= arr[j] 從右邊開始往左邊找到第一個大于k的數(shù)并且放到 arr[i]中
while (i < j && k >= [arrSort[j] intValue]) {
j--;
}
arrSort[i] = arrSort[j];
// k <= arr[j] 從左邊開始往右邊找到第一個小于k的數(shù)并且放到 arr[j]中
while (i<j && k <= [arrSort[i] intValue]) {
i++;
}
arrSort[j] = arrSort[i];
}
arrSort[i] = @(k);
[self quickSort:arrSort leftIndex:left rightIndex:i-1];
[self quickSort:arrSort leftIndex:i+1 rightIndex:right];
}
