9.8.4 非递归实现归并排序 我们常说,“没有最好,只有更好。”归并排序大量引用了递归,尽管在代码上比较清晰,容易理解,但这会造成时间和空间上的性能损耗。我们排序追求的就是效率,有没有可能将递归转化成迭代呢?结论当然是可以的,而且改动之后,性能上进一步提高了。来看代码。
/* 对顺序表L作归并非递归排序 */ 1 void MergeSort2(SqList *L) 2 { 3 int* TR=(int*)malloc(L->length * sizeof(int)); /* 申请额外空间 */ 4 int k=1; 5 while(k
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。
5) 第8行,k=2 6) 第9行,MergePass函数将TR中已经两两归并的有序序列再次归并回数组L.r中,如图9-8-12。
7) 第10行,k=4,因为k<9,所以继续循环,再次归并,最终执行完第7~10行,k=16,结束循环,完成排序工作。如图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 i=i+2*s; 9 } 10 if(i
4) 第10~14行,主要是处理最后的尾数的,第11行是说将最后剩下的多个记录归并到TR中。不过由于i=9,n-s+1=9,因此执行第13~14行,将20放入到TR数组的最后。
5) 再次调用MergePass时,s=2,第5~9行的循环,由第8行的i=i+2*s可知,此时i就是以4为增量进行循环了。也就是说,是将两个有两个记录的有序序列进行归并为四个记录的有序序列。最终再将最后剩下的第九条记录“20”插入TR。
6) 后面的类似,略。 非递归的迭代方法,避免了递归时深度为log2n的栈空间,空间只是用到申请归并临时用的TR数组,因此空间复杂度为O(n)。并且避免递归也在时间性能上有一定的提升,应该说,使用归并排序时,尽量考虑用非递归方法。
最新评论