归并排序
来源：程序员人生 发布时间：2014-09-10 01:18:40 阅读次数：2267次
归并排序的核心思想是分治原则：即将问题分解、解决、合并。问题分解师将n个元素分成n/2个元素的子序列；问题解决是用合并排序法对两个子序列进行递归排序；问题合并是利用已排好的两个子序列合并为新的序列，得到排序结果。可以看出，对已序序列的合并是问题关键。
1.合并已序序列：过程用图来表示吧！
#define INFTY 2147483647
void Merge(int a[],int low,int mid,int high){
int n1 = mid - low+1 , n2 = high - mid;
int* L = new int [n1+1]; //多一个哨兵元素，便于简化代码
int* R = new int [n2+1]; //多一个哨兵元素，便于简化代码
for(int i = 0;i < n1;++i){
L[i] = a[low + i];
}
for(int j = 0;j< n2;++j){
R[j] = a[mid + j+1];
}
L[n1] = INFTY; //哨兵元素值为正无穷
R[n2] = INFTY;
for(int i = 0,j = 0,k = low;k <= high; ++k){ //用于合并数组
if(L[i] <= R[j]){
a[k] = L[i];
++i;
}
else{
a[k] = R[j];
++j;
}
}
delete L;
delete R;
}
开始是右序列R的第一个元素1与左序列L的第一个元素比较，由于1小于2，则将R中的1放置在归并后的数组中，接下来比较L中值为2的元素和R中值为2的元素，结果相等，将L中的2放置在归并后的数组中，以此类推。
代码如下：
2.
归并排序：
代码：
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); //合并左右数组排序结果
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
