9.8.3 非递归实现归并排序(1)
我们常说,“没有最好,只有更好。”归并排序大量引用了递归,尽管在代码上比较清晰,容易理解,但这会造成时间和空间上的性能损耗。我们排序追求的就是效率,有没有可能将递归转化成迭代呢?结论当然是可以的,而且改动之后,性能上进一步提高了,来看代码。
- /* 对顺序表L作归并非递归排序 */
- 1 void MergeSort2(SqList *L)
- 2 {
- 3 int* TR=(int*)malloc(L->length*sizeof(int));/*申请额外空间*/
- 4 int k=1;
- 5 while(k<L->length)
- 6 {
- 7 MergePass(L->r,TR,k,L->length);
- 8 k=2*k; /* 子序列长度加倍 */
- 9 MergePass(TR,L->r,k,L->length);
- 10 k=2*k; /* 子序列长度加倍 */
- 11 }
- 12 }
1.程序开始执行,数组L为{50,10,90,30,70,40,80,60,20},L.length=9。
2.第3行,我们事先申请了额外的数组内存空间,用来存放归并结果。
3.第5~11行,是一个while循环,目的是不断地归并有序序列。注意k值的变化,第8行与第10行,在不断循环中,它将由1→2→4→8→16,跳出循环。
4.第7行,此时k=1,MergePass函数将原来的无序数组两两归并入TR(此函数代码稍后再讲),如图9‐8‐11所示。
![]() |
图9-8-11 |
5.第8行,k=2。
6.第9行,MergePass函数将TR中已经两两归并的有序序列再次归并回数组L.r中,如图9‐8‐12所示。
![]() |
(点击查看大图)图9-8-12 |
![]() |
(点击查看大图)图9-8-13 |
从代码中,我们能够感受到,非递归的迭代做法更加直截了当,从最小的序列开始归并直至完成。不需要像归并的递归算法一样,需要先拆分递归,再归并退出递归。
现在我们来看MergePass代码是如何实现的。
- /* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
- 1 void MergePass(int SR[],int TR[],int s,int n)
- 2 {
- 3 int i=1;
- 4 int j;
- 5 while(i <= n-2*s+1)
- 6 {
- 7 Merge(SR,TR,i,i+s-1,i+2*s-1); /* 两两归并 */
- 8 ii=i+2*s;
- 9 }
- 10 if(i<n-s+1) /* 归并最后两个序列 */
- 11 Merge(SR,TR,i,i+s-1,n);
- 12 else /* 若最后只剩下单个子序列 */
- 13 for(j =i;j <= n;j++)
- 14 TR[j] = SR[j];
- 15 }
联系客服