- 引自百度百科
快速排序由C. A. R. Hoare在1962年提出跋选。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小秽梅，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列研铆。
- 算法介紹
設(shè)要排序的數(shù)組是Array[0]……Array[N-1]比勉，首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)猾骡，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面敷搪，這個(gè)過(guò)程稱為一趟快速排序兴想。值得注意的是，快速排序不是一種穩(wěn)定的排序算法赡勘，也就是說(shuō)嫂便，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)。
一趟快速排序的步驟：
1）設(shè)置兩個(gè)變量i闸与、j，排序開始的時(shí)候：i=0践樱，j=N-1；
2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)袱院，賦值給key，即key=Array[0]；
3）從j開始向前搜索忽洛，即由后開始向前搜索(j--)腻惠，找到第一個(gè)小于等于key的值A(chǔ)rray[j]欲虚，將Array[j]的值賦給Array[i]；
4）從i開始向后搜索复哆，即由前開始向后搜索(i++)欣喧，找到第一個(gè)大于等于key的Array[i]，將Array[i]的值賦給Array[j]梯找；
5）重復(fù)第3、4步初肉，直到i=j； (3,4步中臼隔，沒找到符合條件的值妄壶，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值丁寄，使得j=j-1，i=i+1伊磺，直至找到為止屑埋。找到符合條件的值，進(jìn)行交換的時(shí)候i摘能， j指針位置不變。另外严望，i==j這一過(guò)程一定正好是i+或j-完成的時(shí)候逻恐，此時(shí)令循環(huán)結(jié)束）峻黍。
過(guò)程演示
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 6 | 2 | 7 | 3 | 8 | 9 |
i=0, j=5, k=6
創(chuàng)建變量i=0（指向第一個(gè)數(shù)據(jù)）, j=5(指向最后一個(gè)數(shù)據(jù)), k=6(賦值為第一個(gè)數(shù)據(jù)的值)奸披。
我們要把所有比k小的數(shù)移動(dòng)到k的左面涮雷，所以我們可以開始尋找比6小的數(shù)轻局，從j開始，從右往左找仑扑，不斷遞減變量j的值，我們找到第一個(gè)下標(biāo)3的數(shù)據(jù)比6小蜓竹，于是把數(shù)據(jù)3移到下標(biāo)0的位置储藐，把下標(biāo)0的數(shù)據(jù)6移到下標(biāo)3，完成第一次比較：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 3 | 2 | 7 | 6 | 8 | 9 |
i=0, j=3, k=6
接著蛛碌，開始第二次比較辖源，這次要變成找比k大的了，而且要從前往后找了酝蜒。遞加變量i矾湃，發(fā)現(xiàn)下標(biāo)2的數(shù)據(jù)是第一個(gè)比k大的，于是用下標(biāo)2的數(shù)據(jù)7和j指向的下標(biāo)3的數(shù)據(jù)的6做交換洲尊，數(shù)據(jù)狀態(tài)變成下表：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 3 | 2 | 6 | 7 | 8 | 9 |
i=2, j=3, k=6
稱上面兩次比較為一個(gè)循環(huán)坞嘀。
接著，再遞減變量j丽涩，不斷重復(fù)進(jìn)行上面的循環(huán)比較裁蚁。
本例中進(jìn)行一次循環(huán)后继准，j--移必，得到i==j，一次快排結(jié)束
注意：第一遍快速排序不會(huì)直接得到最終結(jié)果崔泵，只會(huì)把比k大和比k小的數(shù)分到k的兩邊。為了得到最后結(jié)果入篮，需要再次對(duì)k值兩邊的數(shù)組分別執(zhí)行此步驟幌甘，然后再分解數(shù)組，直到數(shù)組不能再分解為止（只有一個(gè)數(shù)據(jù)）锅风，才能得到正確結(jié)果遏弱。
- C語(yǔ)言實(shí)現(xiàn)
void quickSort(int *array, int leftIndex, int rightIndex) {
if(leftIndex >= rightIndex) {/*如果左邊索引大于或者等于右邊的索引就代表已經(jīng)整理完成一個(gè)組了*/
return ;
}
int i = leftIndex;
int j = rightIndex;
int key = array[leftIndex];
while(i < j) {/*控制在當(dāng)組內(nèi)尋找一遍*/
while(i < j && array[j] >= key) {
/*而尋找結(jié)束的條件就是，1漱逸、找到一個(gè)小于或者大于key的數(shù)（大于或小于取決于你想升
序還是降序）2、沒有符合條件1的肮砾，并且i與j的大小沒有反轉(zhuǎn)*/
j--;/*向前尋找*/
}
array[i] = array[j];
/*找到一個(gè)這樣的數(shù)后就把它賦給前面的被拿走的i的值（如果第一次循環(huán)且key是
array[left]袋坑，那么就是給key）*/
while(i < j && array[i] <= key) {
/*這是i在當(dāng)組內(nèi)向前尋找，同上婆誓，不過(guò)注意與key的大小關(guān)系停止循環(huán)和上面相反也颤，
因?yàn)榕判蛩枷胧前褦?shù)往兩邊扔，所以左右兩邊的數(shù)大小與key的關(guān)系相反*/
i++;
}
array[j] = array[i];
}
array[i] = key;/*當(dāng)在當(dāng)組內(nèi)找完一遍以后就把中間數(shù)key回歸*/
quickSort(array, leftIndex, i - 1);/*最后用同樣的方式對(duì)分出來(lái)的左邊的小組進(jìn)行同上的做法*/
quickSort(array, i + 1, rightIndex);/*用同樣的方式對(duì)分出來(lái)的右邊的小組進(jìn)行同上的做法*/
/*當(dāng)然最后可能會(huì)出現(xiàn)很多分左右文留，直到每一組的i = j 為止*/
}
- OC實(shí)現(xiàn)
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
if (leftIndex >= rightIndex) {//如果數(shù)組長(zhǎng)度為0或1時(shí)返回
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)在右邊查找到一個(gè)比基準(zhǔn)數(shù)小的值時(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í)間復(fù)雜度
最好和平均的時(shí)間復(fù)雜度為O(nlogn)
最壞的時(shí)間復(fù)雜度為O(n^2)
