归并排序（Merge Sort）

1. 算法描述

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为归并。

把长度为n的输入序列分成两个长度为n/2的子序列;
对这两个子序列分别采用归并排序(递归拆分数组)；
将两个排序好的子序列,排序合并成一个有序的序列;

2. 过程演示

Merge Sort.gif

归并排序

原始数据

34 54  12  78 3  45  9  

第一步拆分数据

  [34 54  12 ] 
       |
 [34] , [54 12]
       |     
   [54] , [12]  


  [78 3  45  9]  
        |
[78 3] ,  [45  9]  
     |       |
[78],[3]   [45],[9]


第二步合并排序数据

[54],[12] -> [12,54]

[12,54],[34] -> [12,34,54]


[78],[3] -> [3,78]

[45],[9] -> [9,45]

[3,78],[9,45] -> [3,9,,45,78];


[12,34,54],[3,9,45,78] -> [3,9,12,34,45,54,78]

我只写最后两个子序列的排序合并过程

A[]
a[12,34,54]
b[3,9,45,78] 

A[3]
a[12,34,54]
b[9,45,78] 

A[3,9]
a[12,34,54]
b[45,78] 

A[3,9,12]
a[34,54]
b[45,78] 

A[3,9,12,34]
a[54]
b[45,78] 


A[3,9,12,34,45]
a[54]
b[78] 


A[3,9,12,34,45,54]
a[]
b[78] 

A[3,9,12,34,45,54,78]
a[]
b[]

3. 代码实现

- (NSArray *)mergeSort:(NSArray *)sortArray {
    
    if (sortArray.count == 1) {
        return sortArray;
    }
    // 采用 递归实现
    NSInteger length = sortArray.count;
    
    NSInteger middle = length / 2;
    
    NSMutableArray *left = [sortArray subarrayWithRange:NSMakeRange(0, middle)].mutableCopy;
    NSMutableArray *right = [sortArray subarrayWithRange:NSMakeRange(middle,length - middle)].mutableCopy;
    
    // 拆分数组  直到最小份
    NSArray* l =  [self mergeSort:left];
    NSArray* r = [self mergeSort:right];
    
    return [self merge:l right:r];
}

- (NSArray *)merge:(NSArray *)left right:(NSArray *)right {
    
    // 排序 并合并两个个数组
    NSMutableArray *l = left.mutableCopy;
    NSMutableArray *r = right.mutableCopy;
    NSMutableArray *sort = [NSMutableArray array];
    while (l.count > 0 && r.count > 0) {
        if ([l[0] integerValue] < [r[0] integerValue]) {
            [sort addObject:l[0]];
            [l removeObjectAtIndex:0];
        } else {
            [sort addObject:r[0]];
            [r removeObjectAtIndex:0];
        }
    }
    
    while (l.count > 0) {
        [sort addObject:l[0]];
        [l removeObjectAtIndex:0];
    }
    
    while (r.count > 0) {
        [sort addObject:r[0]];
        [r removeObjectAtIndex:0];
    }
    return sort.copy;
}

4. 验证

NSArray *arr = [self pakageNumber:1000];  // 1000个随机数
NSArray *arr1 = [self mergeSort:arr];
count1  :999                        // 外层循环
count2 :9979                      // 内层循环

一万条数据所用时间
time:0.058902;