1
//
C语言实现
2
3
void
mergeSort(
int
array[],
int
first,
int
last)
4
{
5
if
(first < last)
//
拆分数列中元素只剩下两个的时候，不再拆分
6
{
7
int
mid = (first + last) /
2
;
8
//
递归拆分数组
9
mergeSort(array, first, mid);
10
mergeSort(array, mid +
1
, last);
11
//
归并两个数组
12
merge(array, first, mid, last);
13
}
14
}
15
16
void
merge(
int
array[],
int
first,
int
mid,
int
last)
17
{
18
int
i = first, j = mid +
1
, k =
first;
19
int
temp[last +
1
];
20
21
//
从两个数列的第一个开始判断
22
while
(i <= mid && j <=
last)
23
if
(array[i] <=
array[j])
24
temp[k ++] = array[i ++
];
25
else
26
temp[k ++] = array[j ++
];
27
28
//
如果有剩余，补充进入数组
29
while
(i <=
mid)
30
temp[k ++] = array[i ++
];
31
while
(j <=
last)
32
temp[k ++] = array[j ++
];
33
34
//
复制数组
35
while
(first <=
last)
36
{
37
array[first] =
temp[first];
38
first ++
;
39
}
40
}
1
//
Objective-C实现
2
//
通过NSMutableArray的Category实现
3
4
//
.h文件
5
@interface
NSMutableArray (ArraySort)
6
7
- (
void
)mergeSort;
8
9
@end
10
11
//
.m文件
12
13
#import
"
NSMutableArray+ArraySort.h
"
14
15
@implementation
NSMutableArray (ArraySort)
16
17
- (
void
)mergeSort
18
{
19
[self sortByStartIndex:
0
endIndex:self.count -
1
];
20
}
21
22
- (
void
)sortByStartIndex:(
int
)start endIndex:(
int
)end
23
{
24
if
(start <
end)
25
{
26
int
mid = (start + end) /
2
;
27
[self sortByStartIndex:start endIndex:mid];
28
[self sortByStartIndex:mid +
1
endIndex:end];
29
[self mergeByStartIndex:start midIndex:mid endIndex:end];
30
}
31
}
32
33
- (
void
)mergeByStartIndex:(
int
)start midIndex:(
int
)mid endIndex:(
int
)end
34
{
35
int
i = start,j = mid +
1
;
36
NSMutableArray *tempArray = [[NSMutableArray alloc] initWithCapacity:end +
1
];
37
38
while
(i <= mid && j <=
end)
39
if
([[self objectAtIndex:i] integerValue] <=
[[self objectAtIndex:j] integerValue])
40
[tempArray addObject:[self objectAtIndex:i ++
]];
41
else
42
[tempArray addObject:[self objectAtIndex:j ++
]];
43
44
while
(i <=
mid)
45
[tempArray addObject:[self objectAtIndex:i ++
]];
46
while
(j <=
end)
47
[tempArray addObject:[self objectAtIndex:j ++
]];
48
49
for
(
id
object
in
tempArray)
50
[self replaceObjectAtIndex:start++ withObject:
object
];
51
}
52
53
@end
