【问题描述】
利用合并排序算法对一个具有n个整数元素的数组进行排序；（n<100）
【输入形式】
输入两行，第一行为一个整数n，第二行为n个数组元素，n个元素中间用空格隔开。
【输出形式】
输出一行，排好序的数组（元素之间用一个空格隔开）。
【样例输入】
8
8 9 0 1 2 5 4 3
【样例输出】
0 1 2 3 4 5 8 9
【代码展示】
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void Merge(int B[],int C[],int A[],int p,int q)
{
int i=0,j=0,k=0;
while(i<p&&j<q) //两个子序列首元素做比较，小者取出置入父序列
{
if(C[i]<=A[j])
B[k++]=C[i++];
else
B[k++]=A[j++];
}
while(i<p) //将左半部分剩余元素置入父序列
{
B[k++]=C[i++];
}
while(j<q) //将右半部分剩余元素置入父序列
{
B[k++]=A[j++];
}
}
void Mergesort(int A[],int n)
{
int i,j;
if(n>1)
{
int B[100]; //左半部分
int C[100]; //右半部分
int mid=n/2;
for(i=0;i<mid;i++)
B[i]=A[i]; //建立临时数组存储左半部分序列
for(j=mid;j<n;j++)
C[j-mid]=A[j]; //建立临时数组存储右半部分序列
Mergesort(B,mid); //调用自身对左半部分进行合并排序
Mergesort(C,n-mid); //调用自身对右半部分进行合并排序
Merge(A,B,C,mid,n-mid);
}
}
int main()
{
int i,n;
int a[100];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
Mergesort(a,n);
for(i=0; i<n; i++)
{
printf("%d ",a[i]);
}
return 0;
}
8
8 9 0 1 2 5 4 3
0 1 2 3 4 5 8 9