7.5归并排序
假定待排序表含有n个记录,则可以看成n个有序的子表,每个子表长度为1,然后两两归并,得到[n/2]个长度为2或者1的有序表;再两两归并,……如此重复,直到合并成一个长度为n的有序表为止,这种排序方法称为2-路归并排序。
/*归并函数*/
ELemtype *B=(ElemType*)malloc((n+1)sizeof(ElemType)); //辅助数组(动态存储)
void Merge(ElemType A[],int low,int mid,int hign){
for(int k=low;k<=high;k++) //将A数组复制到B数组
B[K]=A[K];
for(int i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){//数组左右两段比较大小排序;
if(B[i]<=B[j])
A[K]=B[i++];
else
A[k]=B[j++];
}
while(i<=mid) A[k++]=B[i++]; //左段没用完
while(j<=high) A[K++]=B[j++]; //右段没用完
}
/*归并排序函数*/
void MergeSort(ElemType A[],int low,int hign){
if(low<high){
int mid=(high+low)/2;
MergeSort(A,low,mid);
MergeSort(A,mid+1,high);
Merge(A,low,mid,high);
}
}