? ? ? ? 單獨(dú)搞一篇文章來(lái)說(shuō)快速排序，是因?yàn)橥瑸镺(N*logN)的幾種排序方法中效率較高，再加上快速排序思想----分治法也確實(shí)實(shí)用。
? ? ? ? 快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。
該方法的基本思想是：
1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)。
2．分區(qū)過(guò)程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。
分析:以一個(gè)數(shù)組作為示例，取區(qū)間第一個(gè)數(shù)為基準(zhǔn)數(shù)。
初始值，i ＝ 0； j ＝ 7； x = arr[i] = 44;
由于已經(jīng)將arr[0]中的數(shù)保存到X中，可以理解成在數(shù)組arr[0]上挖了個(gè)坑，可以將其它數(shù)據(jù)填充到這來(lái)。
? ? ? ? 從j開(kāi)始向前找一個(gè)比X小或等于X的數(shù)。當(dāng)j=6，符合條件，將arr[6]挖出再填到上一個(gè)坑arr[0]中。這樣一個(gè)坑arr[0]就被搞定了，但又形成了一個(gè)新坑arr[6],再找數(shù)字來(lái)填arr[6]這個(gè)坑。這次從i開(kāi)始向后找一個(gè)大于X的數(shù)，當(dāng)i=2，符合條件，將arr[2]挖出再填到上一個(gè)坑中a[6]=a[2]; j--;
? ? ? ? 在這個(gè)過(guò)程中是重要保證與上一個(gè)坑,坑在右邊找最大,坑在左邊找最小。
執(zhí)行完上邊數(shù)組變?yōu)椋?/p>
當(dāng)前值，i ＝ 2；j ＝ 5； X = 44;?
再重復(fù)上邊的步驟,先從后向前找,在從前向后找。
從j開(kāi)始找，當(dāng)j ＝ 1，符合條件，但是j <= i ,所以arr[1]不變,將X填入坑內(nèi),arr[2] = X;
執(zhí)行完上邊數(shù)組變?yōu)椋?br>
到此我們發(fā)現(xiàn)arr[2]前邊的都小于他,后邊的都大于他。因此再對(duì)a[0…2]和a[3…7]這二個(gè)子區(qū)間重復(fù)上述步驟就可以了。
以下是以中間值作為基準(zhǔn)數(shù)的代碼:
- (NSArray*)insertion_sortWithArray:(NSMutableArray*)array low:(NSInteger)low high:(NSInteger)high {? ?
?if(array == nil || array.count == 0){? ? ? ? return nil;? ? }? ? if (low >= high) {? ? ? ? return nil;? ? }? ??
? ? //取中值??
? NSInteger middle = low + (high - low)/2;? ?
? NSNumber *prmt = array[middle];? ?
? NSInteger i = low;??
? NSInteger j = high;? ??
? ? //開(kāi)始排序，使得leftprmt
while (i <= j) {
//? ? ? ? while ([array[i] compare:prmt] == NSOrderedAscending) {? 該行與下一行作用相同
while ([array[i] intValue] < [prmt intValue]) {
i++;
}
//? ? ? ? while ([array[j] compare:prmt] == NSOrderedDescending) { 該行與下一行作用相同
while ([array[j] intValue] > [prmt intValue]) {
j--;
}
if(i <= j){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i++;
j--;
}
}
if (low < j) {
[self insertion_sortWithArray:array low:low high:j];
}
if (high > i) {
[self insertion_sortWithArray:array low:i high:high];
}
return array;
}
輸出結(jié)果為:
NSMutableArray *a= @[@6, @2, @4, @1, @5, @9].mutableCopy;
NSLog(@"%@\n",a);
NSArray *sortA = [self insertion_sortWithArray:a low:0 high:a.count - 1];
NSLog(@"%@",sortA);
