归并排序
归并排序的核心思想还是蛮简单的。如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
代码实现如下：
@interface DMMergeSort : NSObject
// 归并排序
- (void)mergeSort:(NSMutableArray *)dataArray;
@end
@implementation DMMergeSort
- (void)mergeSort:(NSMutableArray *)dataArray
{
NSLog(@"归并排序前：%@", dataArray);
if ([dataArray count] > 1) {
[self mergeSort:dataArray startIndex:0 endIndex:[dataArray count] - 1];
}
NSLog(@"归并排序后：%@", dataArray);
}
- (void)mergeSort:(NSMutableArray *)dataArray startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex
{
// 递归终止条件
if (startIndex >= endIndex) {
return;
}
// 取 startIndex到endIndex之间的中间位置
NSInteger tmpIndex = startIndex + (endIndex - startIndex) / 2;
// 分治递归
[self mergeSort:dataArray startIndex:startIndex endIndex:tmpIndex];
[self mergeSort:dataArray startIndex:tmpIndex + 1 endIndex:endIndex];
// 将 有序数组startIndex...tmpIndex 和 有序数组tmpIndex + 1...endIndex 合并为 startIndex...endIndex 有序
[self merge:dataArray startIndex:startIndex midIndex:tmpIndex endIndex:endIndex];
}
- (void)merge:(NSMutableArray *)dataArray startIndex:(NSInteger)startIndex midIndex:(NSInteger)midIndex endIndex:(NSInteger)endIndex
{
NSMutableArray *tmpArray = [[NSMutableArray alloc] init];
NSInteger i = startIndex;
NSInteger j = midIndex + 1;
while (i <= midIndex && j <= endIndex) {
NSNumber *numOne = [dataArray objectAtIndex:i];
NSNumber *numTwo = [dataArray objectAtIndex:j];
if ([numOne integerValue] <= [numTwo integerValue]) {
[tmpArray addObject:numOne];
i++;
} else {
[tmpArray addObject:numTwo];
j++;
}
}
// 判断那个子数组中有剩余的数据
if (i > midIndex) {
// 将剩余的数据拷贝到临时数组tmp
while (j <= endIndex) {
NSNumber *num = [dataArray objectAtIndex:j];
[tmpArray addObject:num];
j++;
}
} else {
// 将剩余的数据拷贝到临时数组tmp
while (i <= midIndex) {
NSNumber *num = [dataArray objectAtIndex:i];
[tmpArray addObject:num];
i++;
}
}
// 将tmp中的数据拷贝回数组dataArray中,下标startIndex...endIndex
for (NSInteger i = startIndex, j = 0; i <= endIndex; i++, j++) {
[dataArray replaceObjectAtIndex:i withObject:[tmpArray objectAtIndex:j]];
}
}
@end
@interface DMSortDemo : NSObject
@end
@implementation DMSortDemo
- (void)demo
{
// 归并排序
DMMergeSort *mergeSort = [[DMMergeSort alloc] init];
{
NSMutableArray *dataArray = [[NSMutableArray alloc] init];
[dataArray addObject:[NSNumber numberWithInteger:11]];
[dataArray addObject:[NSNumber numberWithInteger:8]];
[dataArray addObject:[NSNumber numberWithInteger:3]];
[dataArray addObject:[NSNumber numberWithInteger:9]];
[dataArray addObject:[NSNumber numberWithInteger:7]];
[dataArray addObject:[NSNumber numberWithInteger:1]];
[dataArray addObject:[NSNumber numberWithInteger:2]];
[dataArray addObject:[NSNumber numberWithInteger:5]];
[mergeSort mergeSort:dataArray];
}
{
NSMutableArray *dataArray = [[NSMutableArray alloc] init];
[dataArray addObject:[NSNumber numberWithInteger:4]];
[dataArray addObject:[NSNumber numberWithInteger:5]];
[dataArray addObject:[NSNumber numberWithInteger:6]];
[dataArray addObject:[NSNumber numberWithInteger:1]];
[dataArray addObject:[NSNumber numberWithInteger:3]];
[dataArray addObject:[NSNumber numberWithInteger:2]];
[mergeSort mergeSort:dataArray];
}
}
@end
方法 - (void)merge:(NSMutableArray *)dataArray startIndex:(NSInteger)startIndex midIndex:(NSInteger)midIndex endIndex:(NSInteger)endIndex 的作用就是，将已经有序的A[p...q]和A[q+1...r]合并成一个有序的数组，并且放入A[p...r]。
如下图所示，申请一个临时数组tmp，大小与A[p...r]相同。用两个游标i和j，分别指向A[p...q]和A[q+1...r]的第一个元素。比较这两个元素A[i]和A[j],如果A[i] <= A[j]，就把A[i]放入到临时数组tmp，并且i后移一位，否则将A[j]放入到临时数组tmp，并且j后移一位。
继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组tmp中的数据拷贝到原数组A[p...r]中。
归并排序的性能分析
第一，归并排序是稳定的排序算法吗？
归并排序稳不稳定关键看merge方法，也就是两个有序数组合并成一个有序数组的那部分代码实现。在合并的过程中，如果A[p...q]和A[q+1...r]之间有值相同的元素，先把A[p...q]中的元素放入tmp数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。
第二，归并排序的时间复杂度是多少？
归并排序的执行效率与要排序的原始数据的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)。
第三，归并排序的空间复杂度是多少？
在任意时刻，只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小，所以空间复杂度是O(n)。
网友评论