#include <stdio.h>
#define N 9
#define MAXSIZE 10000 /* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
int r[MAXSIZE+1]; /* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
int length; /* 用于记录顺序表的长度 */
}SqList;
/* 归并排序********************************** */
/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{
int j,k,l;
for(j=m+1,k=i;i<=m && j<=n;k++) /* 将SR中记录由小到大地并入TR */
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if(i<=m)
{
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; /* 将剩余的SR[i..m]复制到TR */
}
if(j<=n)
{
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; /* 将剩余的SR[j..n]复制到TR */
}
}
/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[],int TR1[],int s, int t)
{
int m;
int TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m); /* 递归地将SR[s..m]归并为有序的TR2[s..m] */
MSort(SR,TR2,m+1,t); /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t); /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
}
}
/* 对顺序表L作归并排序 */
void MergeSort(SqList *L)
{
MSort(L->r,L->r,1,L->length);
}
void print(SqList L)
{
int i;
for(i=1;i<L.length;i++)
printf("%d,",L.r[i]);
printf("%d",L.r[i]);
printf("\n");
}
int main(void){
int i;
int d[N]={50,10,90,30,70,40,80,60,20};
SqList l;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
printf("归并排序（递归）:\n");
MergeSort(&l);
print(l);
return 0;
}
