归并排序（非递归）.c

数据结构c语言版中常见的排序的源码

/*下面是采用非递归方式进行归并排序的一个程序*/

void mergesort(int x[],int n)
{
int i,k;
int swap[20];
k=1;
while(k<n)
{merge(x,swap,k,n);
printf("\nk=%d\n",k);
for(i=0;i<n;i++)
{
x[i]=swap[i];
printf("%d ",x[i]);
}
k=2*k;
}
}
int merge(int x[],int swap[],int k,int n)
{
int i,j,ll,u1,l2,u2,m;
ll=0;
m=0;
while(ll+k<n)
{
l2=ll+k;
u1=l2-1;
u2=(l2+k-1<n-1)?l2+k-1:n-1;
for(i=ll,j=l2;i<=u1&&j<=u2;m++)
{
if (x[i]<=x[j])
{
swap[m]=x[i];
i++;
}
else
{
swap[m]=x[j];
j++;
}
}
while(i<=u1)
{swap[m]=x[i];
m++;
i++;
}
while(j<=u2)
{
swap[m]=x[j];
m++;
i++;
}
while(j<=u2)
{
swap[m]=x[j];
m++;
j++;
}
ll=u2+1;
}
for(i=ll;i<n;i++,m++)
swap[m]=x[i];
}
main()
{int i=0,j,a[20],x=0;
printf("\nplease input data(-1 for quit):\n");
/*输入待排序元素，键入－1退出录入*/
while(x!=-1)
{
scanf("%d",&x);
if(x!=-1)
{
a[i]=x;
i++;
}
}
for(j=0;j<=i-1;j++)
printf("%d ",a[j]);
mergesort(a,i);
printf("\nsort out:");
for(j=0;j<=i-1;j++)
printf("%d ",a[j]);
}