17. 数据结构进阶十七排序实现之归并排序
“人生不是一种享乐 , 而是一桩十分沉重的工作。-- 列夫 .托尔斯泰”
我们来看下归并排序。
1. 归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
例如，有初始关键字序列：72,18,53,36,48,31,36，其二路归并排序过程如下所示。
n=7 [72] [18] [53] [36] [48] [31] [36]
一趟归并： [18 72][36 53] [31 48] [36]
二趟归并： [18 3653 72] [31 36 48]
三趟归并： [18 3136 36 48 53 72]
2. 代码实现
代码实现同上面文字描述基本一致。
最后执行如下图1
3. 源码
#include"stdio.h"
#defineElemTypeint
void print(inta[],intn){
for(intj= 0; j<n; j++){
printf("%d",a[j]);
}
}
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf,inti,intm,intn)
{
intj,k;
for(j=m+1,k=i;i<=m&& j <=n ; ++k){
if(r[j]<r[i])rf[k]=r[j++];
elserf[k]=r[i++];
}
while(i<=m) rf[k++] =r[i++];
while(j<=n) rf[k++] =r[j++];
// print(rf,n+1);
}
void MergeSort(ElemType *r,ElemType *rf,intlenght)
{
intlen = 1;
ElemType*q =r ;
ElemType*tmp ;
while(len<lenght) {
int s= len;
len= 2 * s ;
int i= 0;
while(i+len <lenght){
Merge(q,rf, i, i+ s-1, i+ len-1 );//对等长的两个子表合并
i= i+ len;
}
if(i+ s <lenght){
Merge(q,rf, i, i+ s -1,lenght-1);//对不等长的两个子表合并
}
tmp= q; q = rf;rf =tmp;//交换q,rf，以保证下一趟归并时，仍从q归并到rf
}
}
int main(){
inta[10] = {3,1,5,7,2,4,9,6,10,8};
intb[10];
printf("\n初始化数组输出\n");
print(a,10);
MergeSort(a,b, 10);
printf("\n最后归并算法后输出\n");
print(a,10);
}