归并排序 Merge sort

1、概念

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(nlog n)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。（维基百科）

解题思路

把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。经常被使用的是二路归并算法，即将两个已经排序的序列合并成一个序列的操作。

2）运行过程

①不断地将当前序列平均分割成2个子序列，直到不能再分割(序列中只剩1个元素)
②不断地将2个子序列合并成一个有序序列，直到最终只剩下1个有序序列

image

代码

OC

#import "MergeSore.h"
@interface MergeSore ()
/**
 *
 */
@property (nonatomic, strong) NSMutableArray *leftArray;
@property (nonatomic, strong) NSMutableArray *arrayCopy;
@end

@implementation MergeSore

-(NSArray *)sort:(NSArray *)array{
     _arrayCopy = [NSMutableArray arrayWithArray:array];
    [self divideBeginBegin:0 end:_arrayCopy.count];
    
    return _arrayCopy;
}

-(void)divideBeginBegin:(NSInteger)begin end:(NSInteger)end{
    if (end - begin < 2) return;
    NSInteger mid = (end + begin)/2;
    [self divideBeginBegin:begin end:mid];
    [self divideBeginBegin:mid end:end];
    [self merge:begin mid:mid end:end];
}

-(void)merge:(NSInteger)begin mid:(NSInteger)mid end:(NSInteger)end{
    _leftArray = [NSMutableArray array];
    NSInteger li = 0;
    NSInteger le = mid - begin;
    NSInteger ri = mid;
    NSInteger re = end;
    NSInteger ai = begin;
    for (NSInteger i = 0; i < le; i++) {
        [_leftArray addObject:_arrayCopy[i+ begin]];
    }
 
    while (li < le) {
        if (ri < re && [_arrayCopy[ri] integerValue] < [_leftArray[li] integerValue] ) {
//            _arrayCopy[ai] = _arrayCopy[ri];
//            ai++;
//            ri++;
               _arrayCopy[ai++] = _arrayCopy[ri++];
        }else{
//            _arrayCopy[ai] = _leftArray[li];
//            ai++;
//            li++;
            _arrayCopy[ai++] = _leftArray[li++];
        }
    }
}


@end

java

public void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    int block, start;
        
    for(block = 1; block < len ; block *= 2) {
        for(start = 0; start <len; start += 2 * block) {
            int low = start;
            int mid = (start + block) < len ? (start + block) : len;
            int high = (start + 2 * block) < len ? (start + 2 * block) : len;
            //两个块的起始下标及结束下标
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            //开始对两个block进行归并排序
            while (start1 < end1 && start2 < end2) {
            result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            }
            while(start1 < end1) {
            result[low++] = arr[start1++];
            }
            while(start2 < end2) {
            result[low++] = arr[start2++];
            }
        }
    int[] temp = arr;
    arr = result;
    result = temp;
    }
    result = arr;       
}

三、性能

归并排序的时间复杂度为O(nlogn)；空间复杂度为O(n)；是稳定的排序算法。

归并排序速度仅次于快速排序，为稳定排序算法。一般用于对总体无序，但是各子项相对有序的数列效果比较好。

PS:常见的递推式与复杂度å

image

参考：

维基百科

《恋上算法与数据结构第二季》