序言
上一篇文章我们已经讲完了插入排序，也就是说我的On^2 的算法基本就写完了，当然还有别的On^2 的算法，但是我这里就不一一去介绍了，个人觉得这些基本的排序算法，掌握冒泡、选择、插入排序等基本就够了，今天我们来谈谈高级排序算法归并排序:
自顶向下的归并排序
今天我们会讲两个版本的归并排序，分别是自顶向下和自底向上的，我们先来谈谈自顶向下的归并排序，先看一张图：
根据上面的图片我们就很容易理解自顶向下的归并排序是什么概念了：
自顶向下的排序算法就是把数组元素不断的二分，直到子数组的元素个数为一个，因为这个时候子数组必定是已有序的，然后将两个有序的序列合并成一个新的有序的序列，两个新的有序序列又可以合并成另一个新的有序序列，以此类推，直到合并成一个有序的数组
由于我感觉自己描述的不够清楚，借用一个博客中的话来描述一下，图片也是来自于参考链接，下面会放出参考链接；
好了，下面我们来看下我们的代码实现：
自顶向下归并排序代码实现
#pragma mark - 自顶向下的归并排序
#pragma mark -
- (void)mergeSort:(NSMutableArray *)array {
//对数组从0 -- 数组个数 -1中间的元素进行归并排序
[self __MergeSort:array left:0 right:(int)array.count -1];
}
/**
递归使用归并排序,对arr[left...right]的范围进行排序
@param array 数组
@param left 左边界
@param right 右边界
*/
- (void)__MergeSort:(NSMutableArray *)array left:(int)left right:(int)right {
//判断递归到底的情况
if (left >= right) {
//这时只有一个元素或者是不存在的情况
return;
}
//中间位置的索引
int middle = (right + left) / 2;
//对left - middle区间的元素进行排序操作
[self __MergeSort:array left:left right:middle];
//对middle + 1 - right区间的元素进行排序操作
[self __MergeSort:array left:middle + 1 right:right];
//两边排序完成后进行归并操作
[self merge:array left:left middle:middle right:right];
}
/**
对[left middle] 和 [middle + 1 right]这两个区间归并操作
@param array 传入的数组
@param left 左边界
@param middle 中间位置
@param right 右边界
*/
- (void)merge:(NSMutableArray *)array left:(int)left middle:(int)middle right:(int)right {
//拷贝一个数组出来
NSMutableArray * copyArray = [NSMutableArray arrayWithCapacity:right - left + 1];
for ( int i = left; i <= right; i++) {
//这里要注意由于有left的偏移量 所以copyArray赋值的时候要减去left
copyArray[i - left] = array[i];
}
int i = left,j = middle +1;
//循环从left开始到right区间内给数组重新赋值 注意赋值的时候也是从left开始的不要习惯性写成了从0开始--还有都是闭区间
for (int k = left; k <= right; k++) {
//当左边界超过中间点时 说明左半部分数组越界了 直接取右边部分的数组的第一个元素即可
if (i > middle) {
//给数组赋值 注意偏移量left 因为这里是从left开始的
array[k] = copyArray[j - left];
//索引++
j++;
}else if (j > right) {//当j大于右边的边界时证明有半部分数组越界了，直接取左半部分的第一个元素即可
array[k] = copyArray[i - left];
//索引++
i++;
}else if (copyArray[i - left] > copyArray[j - left]) {//左右两半部分数组比较
//当右半部分数组的第一个元素要小时 给数组赋值为右半部分的第一个元素
array[k] = copyArray[j - left];
//右半部分索引加1
j++;
}else {//右半部分数组首元素大于左半部分数组首元素
array[k] = copyArray[i - left];
i++;
}
}
}
虽然代码中有详细的注释，但是考虑到很多没有任何基础的朋友，我这里简单介绍一下：
1.在- (void)__MergeSort:(NSMutableArray *)array left:(int)left right:(int)right ;这个方法中我们通过递归调用的方式，将整个数组不断的拆分，最终当left >= right也就是拆分到只有一个元素的时候，整个拆分完的部分都是有序的，然后我们在利用- (void)merge:(NSMutableArray *)array left:(int)left middle:(int)middle right:(int)right ；方法通过将两个有序的子数组不断的合并，最终当所有元素都合并完成之后，数组也就有序了；
2.在我们的merge操作也就是合并操作的方法中，我们有一个关键的操作，也就是拷贝一个数组，元素和传入部分的数组元素是一样的，这里也就是整个归并排序的核心，通过比较两个子数组的首元素大小，将小的那个赋值给传入的数组对应的位置，当所有的元素都考察完了，这两个数组也就合并称了一个有序的新数组了。
3.注意在归并操作时 有一个left的便宜俩，也就是复制一个新数组的时候，给新数组赋值的时候注意要减去left的偏移量，在比较的时候同样也要注意减去left的偏移量。
自顶向下归并排序的优化
上面我们已经实现了一个归并排序了，那么我们现在来测试一下：
//生成普通的随机数组
NSMutableArray *normalArray = [self.testHelper generateRandomArray:50000 rangeLeft:1 rangeRight:50000];
//生成近乎有序的排序数组
NSMutableArray *nearArray = [self.testHelper generateNearlyOrderedArray:50000 swapTimes:10];
//普通的随机数组
NSMutableArray *mergeSortNormal = normalArray.mutableCopy;
//近乎有序的数组
NSMutableArray *mergeSortNear = nearArray.mutableCopy;
//插入排序普通数组
NSMutableArray * insertionNormal = normalArray.mutableCopy;
//近乎有序的插入排序数组
NSMutableArray *insertionNear = nearArray.mutableCopy;
NSLog(@"============普通数组插入排序耗时============");
[self.testHelper testSortWithExcuteBlock:^{
[self insertionSort2:insertionNormal];
}];
NSLog(@"============普通数组归并排序耗时============");
[self.testHelper testSortWithExcuteBlock:^{
[self mergeSort:mergeSortNormal];
}];
NSLog(@"============近乎有序插入排序耗时============");
[self.testHelper testSortWithExcuteBlock:^{
[self insertionSort2:insertionNear];
}];
NSLog(@"============近乎有序的归并排序耗时============");
[self.testHelper testSortWithExcuteBlock:^{
[self selectionSort:mergeSortNear];
}];
看完了上面的测试结果，不知道大家是否发现了问题，我们测试发现，对于普通的数组来说归并排序效率比插入排序快很多，但是对于近乎有序的数组来说，插入排序却比归并排序要好的，那么我们的第一个优化就出来了：
1.我们在- (void)__MergeSort:(NSMutableArray *)array left:(int)left right:(int)right ；中递归结束的条件是这样的：
//判断递归到底的情况
if (left >= right) {
//这时只有一个元素或者是不存在的情况
return;
}
当元素比较小的时候，这里我们可以通过使用插入排序来进行排序达到优化：
//归并排序的第1个优化 当是小规模数组的时候使用插入排序
if (right - left <= 15) {//小数值范围的排序使用插入排序，因为会有大量重复的元素 ，而插入排序在重复元素的排序上 效率是相当高的
[self insertionSort3:array left:left right:right];
return;
}
我们看一下优化后的结果：
可以看到虽然还是比不上插入排序，但是很明显已经有一些优化了，下面我们看下一个优化点：
2.我们在merge操作时，直接进行了下面的归并操作：
//两边排序完成后进行归并操作
[self merge:array left:left middle:middle right:right];
我们来分析一下到底有没有必要每次都进行归并操作呢？其实很明显是没有必要的，为什么这么说呢，我们假如要对下面两个数组进行归并：
NSArray *array1 = @[@1,@2,@3,@4];
NSArray *array2 = @[@6,@8,@10,@14];
很明显array1的最后一个元素已经小于array2的第一个元素，那么完全是没有比较进行归并操作的，所以，第二个优化的就这么写：
//优化点2 只有当左半部分的最后一个元素大于右边部分的第一个元素时才归并 否则不归并 因为本来就已经有序了
if (array[middle] > array[middle + 1]) {
//两边排序完成后进行归并操作
[self merge:array left:left middle:middle right:right];
}
从上图可以看到，现在基本上近乎有序的数组也能在很短的时间内就完成了，这得益于我们的两个优化，怎么样，是不是特别有成就感?自己快去试试吧。
自底向上的归并排序
上面我们已经说完了，自顶向下的归并排序，可能你会问了，归并排序还有两种吗？答案是：“没错，就是有两种，刺不刺激？”，不过大家不用担心，接下来要讲的归并排序还是不难的，至少代码量是不多，我们先来看一张图：（也是从别人博客中抠出来的图，有冒犯的话，我立马删除）
下面说一下它的基本概念吧：
自底向上的归并排序算法的思想就是数组中先一个一个归并成两两有序的序列，两两有序的序列归并成四个四个有序的序列，然后四个四个有序的序列归并八个八个有序的序列，以此类推，直到，归并的长度大于整个数组的长度，此时整个数组有序。需要注意的是数组按照归并长度划分，最后一个子数组可能不满足长度要求，这个情况需要特殊处理。自顶下下的归并排序算法一般用递归来实现，而自底向上可以用循环来实现。
下面我们送上代码实现：
#pragma mark - 自底向上的归并排序
#pragma mark -
- (void)mergeBU:(NSMutableArray *)array {
//size是每一次归并的大小 如第一次size为2时就两个元素一组归并 然后依次为size的倍数 4个元素一组 8个元素一组进行归并 直到等于array.count就结束
for (int size = 1; size < array.count; size += size) {
//i表示的是归并时开始的位置，如i= 0 的时候就归并第0个和第一个元素，依次叠加size的两倍，比如size为1且i = 0过后 i就变成了2也即是归并第2个元素和第三个元素，依次又是归并第4个和第五个元素,依次类推，
for (int i = 0; i + size< array.count; i += size + size) {
int middle = i + size - 1;
[self merge:array left:i middle:middle right:(int)MIN(i+size+size - 1, array.count - 1) ];
}
}
}
好了今天就讲到这里了，所有的代码我都会有详细的注释，还有什么不理解的，可以再去看下概念和图片，对比着理解更容易。
参考链接：自顶向下归并排序和自底向上的归并排序
