相关知识
归并排序的非递归思想是将长度为1的子序列合并成长度为2的子序列，然后再将长度为2的子序列合并成长度为4的子序列，直到所有元素合并结束。
?
编程要求
根据提示，在右侧编辑器补充代码，定义三个函数：
（1）Merge函数，用于合并两个有序子段。 将a[low..mid]和a[mid+1..high]两个相邻的有序子序列归并为一个有序子序列a[low..high]。 -void Merge(int a[],int low,int mid,int high);
（2）MergePass函数，这个函数的功能对于长为length数组进行归并，两个两个地合并长度为length的子段。 -void MergePass(int a[],int length,int n); //一趟二路归并排序
（3）MergeSort函数，二路归并算法，调用MergePass函数，length的值依次为1,2,4，...，当length的值大于等于n的时候，归并结束。 -void MergeSort(int a[],int n); //二路归并算法
#include <stdio.h>
#include <stdlib.h>
void input(int *&a,int &n);
void output(int *a,int n);
void Merge(int a[],int low,int mid,int high);
void MergePass(int a[],int length,int n);//一趟二路归并排序
void MergeSort(int a[],int n);//二路归并算法
int main ()
{
int n;
int *a = NULL;
input(a,n);
MergeSort(a,n);
output(a,n);
free(a);
return 0;
}
void input(int *&a,int &n){
scanf("%d",&n);
//动态内存分配
if ((a=(int *)malloc(n * sizeof(int)))==NULL) {
printf("不能成功分配内存单元\n");
exit(0);
}
for (int i=0;i<n;i++)
scanf("%d",&a[i]);
}
void output(int *a,int n){
for (int i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void MergeSort(int a[],int n) {
int gap = 1;
while (gap < n) {
MergePass(a,gap,n);
gap *= 2;
}
}
void MergePass(int a[],int length,int n) {
int i = 0;
while (i < n-2*length+1) {
Merge(a,i,i+length-1,i+2*length-1);
i = i+2*length;
}
if (i+length-1 < n)
Merge(a,i,i+length-1,n-1);
}
void Merge(int a[],int low,int mid,int high) {
int *temp;
int i = low,
j = mid + 1,
k = 0;
printf("%d,%d,%d\n",low,high,mid);
temp = (int *)malloc((high - low + 1) * sizeof(int));
while (i<=mid && j<=high) {
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= mid)
temp[k++] = a[i++];
while (j <= high)
temp[k++] = a[j++];
for (k=0,i=low;i<=high;k++,i++)
a[i] = temp[k];
free(temp);
}测试输入：
10
1 79 70 4 25 1 9 51 11 2
输入说明：
第一行：键盘输入待排序关键的个数
n第二行：输入
n个待排序关键字，用空格分隔数据
预期输出：
0,1,0
2,3,2
4,5,4
6,7,6
8,9,8
0,3,1
4,7,5
8,9,9
0,7,3
0,9,7
1 1 2 4 9 11 25 51 70 79
输出说明：
分行输出两个两个地合并长度为
length的子段时数组元素的下标。 最后一行输出排序的结果，数据之间用一个空格分隔。
运行结果：
