一、归并排序

 归并排序属于分治算法的一种，所谓分而治之，本质就是讲一个大规模的问题分解为若干个规模较小的相同子问题。大致过程如下：

1. 将待排序元素分成大小大致相同的两个子序列
2. 对两个子序列进行排序
3. 将排好序的有序子序列进行合并，得到最终的有序序列

二、算法图解

                            用一张图就可以对这个过程有一个清晰的了解了~

通过这张图就可以清晰的体会到分而治之的思想，就是先把一个无序数组通过递归分成多个小数组，然后对小数组进行排序，再去合并成一个大数组即可。 

 三、具体过程

这时候就说说核心算法的具体实现。首先为了进行合并，引入一个辅助合并函数Merge(),这个函数将排好序的两个子序列A[low, mid]和A[mid+1, high]进行合并（low,high是上下界，mid处于最中间位置）。

先建立一个辅助数组B[]，设置三个辅助指针i，j，k；i和j分别指向两个待排序子序列当前待比较的元素，而k是指向B[]中待放置元素的位置。然后就在while循环中比较A[i]和A[j]，把小的值给B[k]，然后i++, j++，就是指针向后移继续比较，一直到所有的元素比较完后就可以了，这时再把B中的辅助到A数组中即可。对应代码为：

while(i <= mid && j <= high){if(A[i] <= A[j])B[k++] = A[i++];elseB[k++] = A[j++];

主要还是通过递归的方法来解决这个问题

四、实例代码

#include <iostream>
#include <cstdlib>
#include <cstdio> using namespace std;void Merge(int A[], int low, int mid, int high){ //辅助合并数组Merge，该函数将排好序的两个子序列进行合并 int *B = new int[high - low + 1];int i = low, j = mid + 1, k = 0;//开始合并 while(i<=mid && j<=high){if(A[i] > A[j]){//将较小元素放入B数组中 B[k++] = A[j++];} else {B[k++] = A[i++];}}//对剩余的做处理while(i <= mid )	B[k++] = A[i++];while(j <= high )	B[k++] = A[j++];//把B复制到A中for(i = low, k = 0; i<=high; i++){A[i] = B[k++];} delete []B;  //释放空间
}void MergeSort(int A[], int low, int high){if(low < high){  int mid = (low+high)/2;//先划分 MergeSort(A,low,mid);MergeSort(A,mid+1,high);//再合并 Merge(A, low, mid, high);} 
}int main( void ) {int n,A[100];  cout<<"number："<<endl;cin >> n;cout<<"input ："<<endl;for(int i=0; i<n; i++){cin >>A[i]; }MergeSort(A,0,n-1);cout<<"after sort ："<<endl;for(int i=0; i<n; i++){cout<<A[i]<<" ";}return 0;
} 
// 分解简单，合并操作难

时间复杂度：O(nlogn)

五、小结

总的来说，归并排序这个算法综合来看还是比较全面的，性能可以，虽然比快排慢了点，可以从下图看出：

但是在时间复杂度都相同的情况下比快排要稳定，所以这也算是归并的一个优势吧。

原创不易，看完点个赞再走吧（小声bb）