www.bn0099.com:9.8.3 非递归实现归并排序（1）

来源：百度文库 编辑：偶看新闻 时间：2024/04/27 03:52:46

9.8.3 非递归实现归并排序（1）

我们常说，“没有最好，只有更好。”归并排序大量引用了递归，尽管在代码上比较清晰，容易理解，但这会造成时间和空间上的性能损耗。我们排序追求的就是效率，有没有可能将递归转化成迭代呢？结论当然是可以的，而且改动之后，性能上进一步提高了，来看代码。

  1. /* 对顺序表L作归并非递归排序 */  
  2. 1 void MergeSort2（SqList *L）  
  3. 2 {  
  4. 3 int* TR=（int*）malloc（L->length*sizeof（int））;/*申请额外空间*/  
  5. 4 int k=1;  
  6. 5 while（klength）  
  7. 6 {  
  8. 7 MergePass（L->r,TR,k,L->length）;  
  9. 8 k=2*k; /* 子序列长度加倍 */  
  10. 9 MergePass（TR,L->r,k,L->length）;  
  11. 10 k=2*k; /* 子序列长度加倍 */  
  12. 11 }  
  13. 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-127．第10行，k=4，因为k<9，所以继续循环，再次归并，最终执行完第7～10行，k=16，结束循环，完成排序工作，如图9‐8‐13所示。
（点击查看大图）图9-8-13

从代码中，我们能够感受到，非递归的迭代做法更加直截了当，从最小的序列开始归并直至完成。不需要像归并的递归算法一样，需要先拆分递归，再归并退出递归。

现在我们来看MergePass代码是如何实现的。

  1. /* 将SR[]中相邻长度为s的子序列两两归并到TR[] */  
  2. 1 void MergePass（int SR[],int TR[],int s,int n）  
  3. 2 {  
  4. 3 int i=1;  
  5. 4 int j;  
  6. 5 while（i <= n-2*s+1）  
  7. 6 {  
  8. 7 Merge（SR,TR,i,i+s-1,i+2*s-1）; /* 两两归并 */  
  9. 8 ii=i+2*s;  
  10. 9 }  
  11. 10 if（i11 Merge（SR,TR,i,i+s-1,n）;  
  12. 12 else /* 若最后只剩下单个子序列 */  
  13. 13 for（j =i;j <= n;j++）  
  14. 14 TR[j] = SR[j];  
  15. 15 }
归并排序法 实现递归和非递归转换的基本思想是什么？ 谁知道空间复杂度为o(1)的归并排序算法？ 修改归并排序的程序 数据结构 谁会用pascal实现 用后序的顺序创建一个二*树，并对此二*树进行遍历（递归or非递归均可） 递归排序算出1，1，2，3，5，8……的第30个数？ 急:请教关于C++递归实现N数排序问题(不知道为什么溢出了) 这个归并排序为什么在DEV下运行错误？ c++里面的归并排序法怎么写？ 用递归算法实现1-N中任全R个数 ack问题非递归算法 谁有八皇后非递归算法? 二级C公共基础题中的插入排序,选择排序,快速排序,归并排序各有什么特点，具体是怎么回事？ 对照递归算法和非递归算法的优缺点。 所有用递归算法的能不能都用非递归算法实现? 请问如何用ASP实现记录按1、2、3这样排序？？ 如何实现随机排序？？？ C语言汉诺塔 非递归算法 插入，选择，交换，分配，归并排序法那个对文件的初始状态作要求？ 谁帮我解决下归并排序程序的问题///TC环境 一个递归算法的实现问题 c语言 用递归法 对字符串进行排序 气泡排序和选择排序用链表实现 （急）ASP中如何实现栏目排序调整？