归并非递归排序
最编程
2024-07-20 14:58:26
...
/*对顺序表L作归并非递归排序*/
void MergeSort2(SqlList *L)
{
int* TR=(int*)malloc(L->length*sizeof(int)); /*申请额外空间*/
int k=1;
while(k<L->length)
{
MergePass(L->r,TR,k,L->length);
k=2*k; /*子序列长度加倍*/
MergePass(TR,L->r,k,L->length);
k=2*k; /*子序列长度加倍*/
}
}
/*将SR[]中相邻长度的为s的子序列两两归并到TR[]*/
void MergePass(int SR[],int TR[],int s,int n)
{
while(i<=n-2*s+1)
{
Merge(SR,TR,i,i+s-1,i+2*s-1); /*两两归并*/
i=i+2*s;
}
if(i<n-s+1) /*归并最后两个序列*/
Merge(SR,TR,i,i+s-1,n);
else /*若最后只剩下单个子序列*/
for(j=i;j<=n;j++)
TR[j]=SR[j];
}
/*将有序的SR[i…m]和SR[m+1…n]归并为有序的TR[i…n]*/
voidMerge(intSR[],intTR[],inti,intm,intn)
{
intj,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) /*说明SR[i…m]没有完全归并到TR而SR[m+1…n]已经全部归并到SR*/
{
for(l=0;l<=m-i;l++)
TR[k+1]=SR[i+1]; /*将剩余的SR[i…m]复制到TR*/
}
if(j<=n) /*说明SR[m+1…n]没有完全归并到TR而SR[i…m]已经全部归并到SR*/
{
for(l=0;l<=n-j;l++)
TR[k+1]=SR[j+1]; /*将剩余的SR[m+1…n]复制到TR*/
}
}