归并排序

归并排序

归并排序的核心思想还是蛮简单的。如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
代码实现如下：

@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)。