iOS 之快速排序
单独搞一篇文章来说快速排序，是因为同为O(N*logN)的几种排序方法中效率较高，再加上快速排序思想----分治法也确实实用。
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
分析:以一个数组作为示例，取区间第一个数为基准数。
初始值，i ＝ 0； j ＝ 7； x = arr[i] = 44;
由于已经将arr[0]中的数保存到X中，可以理解成在数组arr[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=6，符合条件，将arr[6]挖出再填到上一个坑arr[0]中。这样一个坑arr[0]就被搞定了，但又形成了一个新坑arr[6],再找数字来填arr[6]这个坑。这次从i开始向后找一个大于X的数，当i=2，符合条件，将arr[2]挖出再填到上一个坑中a[6]=a[2]; j--;
在这个过程中是重要保证与上一个坑,坑在右边找最大,坑在左边找最小。
执行完上边数组变为：
当前值，i ＝ 2；j ＝ 5； X = 44;
再重复上边的步骤,先从后向前找,在从前向后找。
从j开始找，当j ＝ 1，符合条件，但是j <= i ,所以arr[1]不变,将X填入坑内,arr[2] = X;
执行完上边数组变为：
到此我们发现arr[2]前边的都小于他,后边的都大于他。因此再对a[0…2]和a[3…7]这二个子区间重复上述步骤就可以了。
以下是以中间值作为基准数的代码:
- (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;
//开始排序，使得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;
}
输出结果为:
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);
