归并排序非递归算法
#include
#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[im]合并到T中
{
for（；i<=m;i++）
T[k++]=S[i];
}
if（j<=n）//将剩余的S[jn]合并到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
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（klength）
{
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;
} |