归并排序(Merge Sort)是一种稳定的排序算法,它基于分治模式来将原来的问题分解为更小的子问题,待求解完子问题后将子问题的解组合起来返回排序好的数组。归并排序在任何情况下,它的复杂度都是O(nlgn),因为问题分解的过程是递归树向下延伸的过程,与原本的序列数并没有关系,树的高度永远是。

而快速排序则具有很大的随机性,它的性能不仅与算法所选取的基准点有关,还与原来的序列数的逆序数的多少相关。因此归并排序更加稳定,在某些逆序数较多的数组上表现得比快速排序好。

为了更好地理解分治地过程,在第一层的分解中,我们就要确定合并子问题解的解决方案:

原来的数组被逻辑上分为两个子数组后,这两个子数组的有序性对合并问题并没有帮助。即使两个子数组完全有序,我们也不能单纯地调换两个数组的前后位置来使原来的数组有序,因此需要开辟与原来的数组等长的额外的两个内存空间来保存两个子数组的有序信息。而算法本身只对原来数组的指针进行操作,因此归并排序还是原地排序算法。如果我们分解后的两个数组并不有序,那么分解便没有意义,因为整个数组的最小值对我们未知,我们仍需要一个元素一个元素地遍历与原数组等长次数才能确认最小元素,但如果分解后的两个数组递增有序,我们只需要比较两个数组中第一个元素的大小,通过指针递增遍历的形式为我们额外开辟的数组以按元素从小到大的顺序赋值。

我们为每个数组引入了哨兵位来防止指针溢出发生未定义的行为,这样算法需要做的就是每次比较左右子树中指针所对应位置的元素大小,然后给额外开辟的数组空间指针指向的元素赋值并右移该指针和指向比较两个数较小数的指针。

为了使得满足大数组分解成递增有序的小数组,我们需要递归对分解后的数组应用此过程,然后返回我们为每个子问题额外开辟的,经排序后有序的数组交给上一层树的子问题使用,这个过程是从树的叶子开始的,直到数组的大小和原数组一致。

在这个过程中,额外开辟的内存是一个不小的消耗,因此每次子问题完成后,对于C/C++这样不支持自动垃圾回收的语言来说需要显式的释放两个子数组的内存。

#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<sstream>#define max 400
#define min -300
#define infinite 1000000using namespace std;void MergeSort(int *a, int p, int r);int *getRandData(int n) {//获取大小为n并且元素在min~max之间的数组int *arr = (int *)malloc(sizeof(int) * n);for (int i = 0; i < n; i++) arr[i] =((rand() %(max-min+1))+min) ;return arr;
}int main(){srand((unsigned)time(NULL));int num=200;int *arr = getRandData(num);for (int i=0;i<200;i++){cout<<*(arr+i)<<" ";}cout<<"\n"<<"After Sorted"<<endl;int gap=num/2;MergeSort(arr,0,num-1);for (int i=0;i<200;i++){cout<<*(arr+i)<<" ";}system("pause");return 0;
}void Merge(int *a, int p, int q, int r)
{int n1 = q-p+1;int n2 = r-q;int *L = new int[n1+1];int *R = new int[n2+1];int i, j, k;for (i=0; i<n1; i++)	L[i] = a[p+i];for (j=0; j<n2; j++)	R[j] = a[q+j+1];L[n1] = infinite;R[n2] = infinite;for (i=0, j=0, k=p; k<=r; k++){if (L[i]<=R[j]){a[k] = L[i];i++;}else{a[k] = R[j];j++;}}delete []L;delete []R;
}void MergeSort(int *a, int p, int r)
{if (p<r){int q = (p+r)/2;MergeSort(a, p, q);MergeSort(a, q+1, r);Merge(a, p, q, r);}
}