归并排序是建立在归并操作上的一种有效的排序算法，算法主要采用分治法（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，如需转载请自行联系原作者
