归并排序

guohai-stronger 2018-06-28 原文

本篇是讲述数据结构的经典排序算法-归并排序。大约只占用5分钟时间，本篇讲述方式将不同于其他博客方式，希望大家可以对归并排序有更深的了解（起码进大公司，可以手写出归并排序）。

一、准备食材

所谓归并就是将两个已经排好序的队列，合成为一个有序队列。英文中一般用merge来形容。

下面是一个待排序数据

我们可以把这些数值，看成若干个独立的队列，而每个队列只含有一个队列，含有一个数据的队列当然是有序的。

现在我们准备两个相邻的两个队列合成一个队列，最后一组不用合并；结果如下：

我们得到的数据在每一个数组内都是有序的，现在每个小组有两个元素，只有最后一个小组有一个元素。然后我们再把相邻的一组进行合并，以此类推……结果如下：

上面是手动的解释归并的大概思想，相信大家有点了解啦。

二、下锅

1.思想

图中已经给出了两个有序的队列，我们把它放在数组中。我们要得到一个新的有序队列，归并的结果需要一个新的存储空间，来存储归并好的这个队列。

（1）首先我们要开辟一个大小为两个待归并之和空间的数组存储空间，如下图

（2）然后两个指针，分别指向待排队列的第一个元素，如下图

然后比较两个指针指向位置值的大小，较小的元素放在新建的队列中，并相应的移动指针，如下图

这个过程可以一直重复下去，直到某一个队列元素耗尽，则另一个队列的剩余元素都拷贝到新队列尾部。如下图

下面我们直接敲代码，用OC的方式。（演示的代码是将两个有序的数组变成一个有序的数组）可以直接运行（里面讲解了思路）

#import "ViewController.h"

@interface ViewController ()

@property (nonatomic,strong)NSMutableArray *arrC;

@end

@implementation ViewController
- (NSMutableArray *)arrC{
    if (!_arrC) {
        _arrC = [NSMutableArray array];
    }
    return _arrC;
}

- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSMutableArray *arrA = [[NSMutableArray alloc]initWithObjects:@(1),@(4),@(5),@(8),@(9),@(15), nil];
    NSMutableArray *arrB = [[NSMutableArray alloc]initWithObjects:@(2),@(7),@(11),@(14), nil];
    
    self.arrC = [self mergeArrWithArrA:arrA withArrB:arrB];
    NSLog(@"%@",self.arrC);
  
}

- (NSMutableArray *) mergeArrWithArrA:(NSMutableArray *)arrA withArrB:(NSMutableArray *)arrB{
    int a_i = 0;//代表数组A指针下标
    int b_i = 0;//代表数组B指针下标
    int c_i = 0;//代表数组C指针下标
    
    //下面是核心代码，请先看第一部分，再看第二部分，最后第三部分
    
    //第二部分：确定循环条件
    while (a_i < arrA.count && b_i <arrB.count) {
        //第一部分：主要是比较
        //分别取出数组A和数组B对应的值比较
        if ([arrA[a_i] integerValue] <= [arrB[b_i]integerValue]) {
            self.arrC[c_i++] = arrA[a_i++];//意思是当小于时，arrA下标递进，继续比较
        }else{
            self.arrC[c_i++] = arrB[b_i++];//意思是当大于时，arrB下标递进，继续比较
        }
    }
    
    //第三部分：处理余下数据
    while (a_i < arrA.count) {
        self.arrC[c_i++] = arrA[a_i++];//数组A没有排完，直接插入尾部（因为数组A有序）
    }
    while (b_i < arrB.count) {
        self.arrC[c_i++] = arrB[b_i++];//数组B没有排完，直接插入尾部（因为数组A有序）
    }
    return self.arrC;
    
}