一、前言
前面我们讲了插入排序，选择排序以及交换排序，感兴趣的话可以看看下面的链接
那么今天我们来讲一讲归并排序
二、归并排序
基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
我们需要新建一个数组空间，用来保存分区间排序后的数据。使用递归的方法可以把数组分为多个小的区间，先使各个小区间有序，然后再使大区间有序。
归并排序的一般思想就是使用递归法实现。
代码实现如下：
void _MergeSort(int* a, int left, int right, int* tmp) { if(left >= right) return; int mid = (left + right) / 2; //[left, mid] [mid+1, right] //分治递归 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid+1, right, tmp); int begin1 = left, end1 = mid; int begin2 = mid+1, end2 = right; int idx = begin1; while(begin1 <= end1 && begin2 <= end2) { if(a[begin1] < a[begin2]) { tmp[idx++] = a[begin1++]; } else { tmp[idx++] = a[begin2++]; } } while(begin1 <= end1) { tmp[idx++] = a[begin1++] } while(begin2 <= end2) { tmp[idx++] = a[begin2++]; } memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1)); } void MergeSort(int* a, int n) { (int*)tmp = (int*)malloc(sizeof(int) * n) if(tmp == NULL) { printf("malloc fail"); exit(-1); } _MergeSort(a, 0, n-1, tmp); free(tmp); }
三、归并排序的非递归思想
归并排序的递归思想是最常用的思想。但是，我们知道一旦有递归，必定会建立新的栈帧。而在实际应用中，如果待排序的数据非常多，那么我们就必须建立更多的栈帧，而内存空间中栈区的内存有限，如果栈帧建立过多就会发生栈溢出，造成风险。因此学习归并排序的非递归就十分有必要了。那么接下来我们就来讲讲归并排序的非递归形式。
无法使用递归，那么我们就来使用循环来帮助我们实现归并排序。那么要怎么来控制循环呢？这是一个难题。其实我们这里就需要借助一个变量gap来帮助我们归并区间的数。具体做法如下：
* gap=1,每次归并 [ i, i+gap-1] [i+gap, i+2*gap-1]两个区间的数。即 [0, 0] [1, 1]归并....
* 然后gap *= 2, 两两归并，即 [0, 1] [2, 3]区间的数归并
* 重复上面的步骤
可能文字描述不是很形象，那么请看下图：
<< 聪明的你一定看出来了，i= 多少那后面的区间我是用红色和黑色区分写的，这是为什么呢？因为红色写的我们需要归并的区间已经超出了数组的区间，但是执行程序时却需要超出，因为那是我们算出来的归并区间。实际上后面超出的区间根本就没有数据，那是不是思路错了呢？当然不是，遇到这种情况我们就需要修正一下区间范围，以防止数组越界。
看明白了上图并且想清楚了上面的问题，那么我们就用代码来实现：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n) if (tmp == NULL) { printf("malloc fail"); exit(-1); } int gap = 1; while(gap < n) { for(int i=0; i < n; i += 2*gap) { //[i, i+gap-1] [i+gap, i+2*gap-1] int begin1 = i, end1 = i+gap-1; int begin2 = i+gap, end2 = i+2*gap-1; //修正边界 if(end1 >= n) { end1 = n-1; //把begin2和end2修正为不存在的区间 begin2 = n; end2 = n-1; } else if(begin2 >= n) { begin2 = n; end2 = n-1; } else if(end2 >= n) { end2 = n-1; } int j = begin1; while(begin1 <= end1 && begin2 <= end2) { if(a[begin1] < a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while(begin1 <= end1) { tmp[j++] = a[begin1]; } while(begin2 <= end2) { tmp[j++] = a[begin2]; } } memcpy(a, tmp, sizeof(int) * n); gap *= 2; } free(tmp); }
下面我们来测试一下归并排序的非递归代码
int main() { int a[10] = { 7,317,96,1,108,6,8,33,55,44 }; int n = sizeof(a) / sizeof(a[0]); MergeSortNonR(a, n); for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
运行结果如下：
好了，归并排序的非递归也成功实现了，实现起来确实有一点点小复杂。那么我们的归并排序的所有都讲完了。
四、归并排序的特性总结
1、归并的缺点在于需要O(N)的空间复杂度，归并排序更多的是解决在磁盘中的外排序问题。
2、时间复杂度：O(N*logN)
3、空间复杂度：O(N)
4、稳定性：稳定
