快速排序
快速排序(Quick Sort) 的基本思想是：通過(guò)一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分协饲，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序做鹰，以達(dá)到整個(gè)序列有序的目的。
動(dòng)效圖如下：
排序思路：
數(shù)組選第一個(gè)數(shù)，把比數(shù)小的放到數(shù)的左邊并扇，比數(shù)大的放到右邊，結(jié)束后對(duì)左右兩邊的數(shù)組作重復(fù)處理即可抡诞。
排序演示：
假設(shè)數(shù)組為 [3穷蛹，6，1昼汗，4肴熏，7，2顷窒，5]
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 排序 | 3 | 6 | 1 | 4 | 7 | 2 | 5 |
以第一個(gè)元素3為基數(shù)蛙吏，從最后一個(gè)元素開(kāi)始查找比3小的數(shù)字，發(fā)現(xiàn)2蹋肮，交換位置：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 排序 | 2 | 6 | 1 | 4 | 7 | 3 | 5 |
從2的右面開(kāi)始與基數(shù)3比找比3大的數(shù)字出刷，找到6，交換位置：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 排序 | 2 | 3 | 1 | 4 | 7 | 6 | 5 |
從6的左邊面開(kāi)始與基數(shù)3比坯辩，找比3小的數(shù)字馁龟，找到1，交換位置：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 排序 | 2 | 1 | 3 | 4 | 7 | 6 | 5 |
結(jié)束第一次排序漆魔，分別開(kāi)始對(duì)3的左右兩邊的數(shù)據(jù)作循環(huán)對(duì)比坷檩，左邊：2與1對(duì)比更改位置：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 排序 | 1 | 2 | 3 | 4 | 7 | 6 | 5 |
左邊結(jié)束。右邊：4為基數(shù)改抡，從右邊開(kāi)始找比4小的數(shù)矢炼，找不到，循環(huán)結(jié)束阿纤，因?yàn)?的左邊已經(jīng)完畢句灌，從4的右邊開(kāi)始，也就是從7開(kāi)始作基數(shù)對(duì)比，找比7小得數(shù)放到7的左面胰锌，找到5骗绕，交換位置：
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 排序 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
從5的右邊查找發(fā)現(xiàn)已經(jīng)有序，循環(huán)結(jié)束资昧。
快速排序代碼：
- (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開(kāi)始查找比基準(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開(kā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];
}
NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
[self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count-1];
打印結(jié)果為：
1, 2, 3, 5, 7, 8, 9, 10, 12, 13, 16
快速排序復(fù)雜度分析：
最優(yōu)的情況下叽唱，時(shí)間復(fù)雜度為O(nlogn),最壞的情況下為O(n2)屈呕。平實(shí)的情況為O(nlogn)。
對(duì)于空間復(fù)雜度來(lái)說(shuō)棺亭，主要是遞歸造成的椓垢ぃ空間的使用，最好情況侦铜，遞歸樹(shù)的深度為log?n,其空間復(fù)雜度也就是O(logn),最壞情況专甩，需要進(jìn)行n-1次遞歸調(diào)用，空間復(fù)雜度為O(n), 平均情況钉稍，空間復(fù)雜度為O(logn)
可惜的是涤躲，由于關(guān)鍵字的比較和交換是跳躍進(jìn)行的，因此贡未，快速排序是一種不穩(wěn)定的排序方法种樱。
上一篇：iOS算法總結(jié)-歸并排序
下一篇：iOS算法總結(jié)-回顧
