归并排序非递归算法

归并排序非递归算法

#include<cstdio>
#include<cstdlib>
#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]<S[j])
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 MergePass(int S[],int T[],int s,int n)//将S[]中长度为s的子序列两两归并到T[]
{
int i=1;
int j;
while(i<=n-2*s+1)
{
Merge(S,T,i,i+s-1,i+2*s-1);//两两归并
i=i+2*s;
}
if(i<n-s+1)//归并最后两个序列
Merge(S,T,i,i+s-1,n);
else//若最后只剩下单个子序列
{
for(j=i;j<=n;j++)
T[j]=S[j];
}
}

void MergeSort(SeqList *L)
{
int k=1;
int *T=(int *)malloc(sizeof(int)*L->length);
if(!T)
{
printf("No enough memory!\n");
exit(-1);
}
while(k<L->length)
{
MergePass(L->Array,T,k,L->length);//子序列加倍
k=k*2;
MergePass(T,L->Array,k,L->length);
k=k*2;
}
}

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;
}