归并
/*
归并排序的思想：
假设初始序列含有n个记录，则可以看成是n个
有序的子序列，每个子序列的长度为1，然后两两
归并，得到n/2个长度为1或者2的有序子序列
在两两归并，如此重复，直到一个长度为n的有序
序列为止
*/
#include
#define MAX 1000
typedef struct seeqlist
{
int Array[MAX];
int length;
}SeqList;
void Merge(int S[],int T[],int i,int m,int n)
{
int j,k;
for(j=m+1,k=i;i<=m&&j<=n;k++)
{
if(S[i] T[k]=S[i++];
else
T[k]=S[j++];
}
if(i<=m)//将剩余的S[i..m]合并到T中
{
for(;i<=m;i++)
T[k++]=S[i];
}
if(j<=n)//将剩余的S[j..n]合并到T中
{
for(;j<=n;j++)
T[k++]=S[j];
}
}
void Msort(int S[],int T[],int s,int t)
{
int T2[MAX];
int m;
if(s==t)
T[s]=S[s];
else
{
m=(s+t)/2;//将S[s..t]平分成S[s..m]和S[m+1..t]
Msort(S,T2,s,m);//递归将S[s..m]归并为T2[s..m]
Msort(S,T2,m+1,t);///递归将S[m+1..t]归并为T2[m+1..t]
Merge(T2,T,s,m,t);//合并
}
}
void MergeSort(SeqList *L)//只是为了保持传参的一致性
{
Msort(L->Array,L->Array,1,L->length);
}
int main(int argc,char *argv[])
{
int i;
SeqList L;
scanf("%d",&L.length);
for(i=1;i<=L.length;i++)
scanf("%d",&L.Array[i]);
MergeSort(&L);
printf("After Sort:\n");
for(i=1;i<=L.length;i++)
printf("%4d",L.Array[i]);
printf("\n");
return 0;
}
排序递归算法