归并排序是建立在归并操作上的一种有效的排序算法，算法主要采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的算法复杂度为O（N*logN），需要的额外的空间跟数组的长度N有关系，实现归并排序最简单的方法是将两个数组重新整合到第三个数组中。通常对于一个数组我们对前半部分进行排序，然后进行后半部分进行排序，实现原地归并操作，不过需要额外的空间存储数组。假设数据中有8个元素，先分为四组进行比较，之后分为两组进行比较，最后分为一组进行比较，这样就衍生出来两种方法，一种是自顶向下的归并排序，一种是自底向上的归并排序。
自顶向下的归并排序
实现起来比较简单，不过merge的稍微麻烦点:
|
1
2
3
4
5
6
7
8
9
10
|
-(void)mergeSort:(NSMutableArray *)arr lowIndex:(NSInteger)low highIndex:(NSInteger)high{
if (high<=low) {
return;
}
NSInteger mid=low+(high-low)/2;
[self mergeSort:arr lowIndex:low highIndex:mid];//左半部分排序
[self mergeSort:arr lowIndex:mid+1 highIndex:high];//右半部分排序
[self merge:arr lowIndex:low highIndex:high midIndex:mid];
} |
merge操作，就是对数组进行比较:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
-(void)merge:(NSMutableArray *)dataSource lowIndex:(NSInteger)low highIndex:(NSInteger)high midIndex:(NSInteger)mid{
NSInteger i=low,j=mid+1;
for (NSInteger k=low; k<=high; k++) {
self.tempArr[k]=dataSource[k];
}
for (NSInteger k=low; k<=high; k++) {
//左边的元素已经取完，取右半边的元素
if (i>mid) {
dataSource[k]= self.tempArr[j++];
}
//右边的元素已经取完，取左边的元素
else if (j>high) {
dataSource[k]= self.tempArr[i++];
}
//如果索引j的值大,那么取左边的值
else if ([self.tempArr[j] integerValue]<[self.tempArr[i] integerValue]) {
dataSource[k]=self.tempArr[j++];
}
else{
dataSource[k]=self.tempArr[i++];
}
}
} |
合并的时候需要给临时数组赋值:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
MySort *sort=[[MySort alloc]init];NSMutableArray *tempArr=[[NSMutableArray alloc]initWithCapacity:10];
for (NSInteger i=0; i<8; i++) {
[tempArr addObject:[NSNull null]];
}NSMutableArray *arr=[[NSMutableArray alloc]initWithCapacity:10];
[arr addObject:@"16"];
[arr addObject:@"3"];
[arr addObject:@"2"];
[arr addObject:@"18"];
[arr addObject:@"19"];
[arr addObject:@"10"];
[arr addObject:@"4"];
[arr addObject:@"25"];
sort.tempArr=tempArr;[sort mergeSort:arr lowIndex:0 highIndex:arr.count-1];for (NSInteger i=0; i<[arr count]; i++) {
NSLog(@"数值:%@",arr[i]);
}NSLog(@"iOS技术交流群:%@",arr[2]);
NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");
|
效果如下:
自底向上的归并排序
自底向上的归并排序其实逻辑跟上一个一样，不过这个不需要递归到最后，直接从一开始就进行比较，通过控制增量解决合并的问题，如果有8个元素，增量为1时有四组(每组两个)合并，增量为2时候，两组（每组四个）合并，最后进行全部合并，代码比较简单:
|
1
2
3
4
5
6
7
8
9
|
-(void)mergeSortBottom:(NSMutableArray *)arr{
NSInteger count=[arr count];
for (NSInteger increment=1; increment<count; increment=increment+increment) {//增量的数组
for (NSInteger low=0; low<count-increment; low+=increment+increment) {//每个增量比较的次数
NSInteger high=(low+increment+increment-1)<(count-1)?(low+increment+increment-1):(count-1);
[self merge:arr lowIndex:low highIndex:high midIndex:low+increment-1];
}
}
} |
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4589954.html，如需转载请自行联系原作者