9.8.3　非递归实现归并排序

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

  1. /* 对顺序表L作归并非递归排序 */
  2. void MergeSort2(SqList *L)
  3. {
  4.     /* 申请额外空间 */
  5.     int * TR = (int *)malloc(L->length * sizeof(int));    
  6.     int k = 1;
  7.     while (k < L->length)
  8.     {
  9.         MergePass(L->r, TR, k, L->length);
  10.         /*子序列长度加倍 */
  11.         k = 2 * k;                                        
  12.         MergePass(TR, L->r, k, L->length);
  13.         /* 子序列长度加倍 */
  14.         k = 2 * k;                                        
  15.     }
  16. }

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.3　非递归实现归并排序 - 图1

图9-8-11

5．第8行，k=2。

6．第9行，MergePass函数将TR中已经两两归并的有序序列再次归并回数组L.r中，如图9-8-12所示。

9.8.3　非递归实现归并排序 - 图2

图9-8-12

7．第10行，k=4，因为k<9，所以继续循环，再次归并，最终执行完第7～10行，k=16，结束循环，完成排序工作，如图9-8-13所示。

9.8.3　非递归实现归并排序 - 图3

图9-8-13

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

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

  1. /* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
  2. void MergePass(int SR[], int TR[], int s, int n)
  3. {
  4.     int i = 1;
  5.     int j;
  6.     while (i <= n - 2 * s + 1)
  7.     {
  8.         /* 两两归并 */
  9.         Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);    
  10.         i = i + 2 * s;
  11.     }
  12.     /* 归并最后两个序列 */
  13.     if (i < n - s + 1)                                 
  14.         Merge(SR, TR, i, i + s - 1, n);
  15.     /* 若最后只剩下单个子序列 */
  16.     else                                               
  17.         for (j = i; j <= n; j++)
  18.             TR[j] = SR[j];
  19. }

1．程序执行。我们第一次调用“MergePass(L.r,TR,k,L.length);”，此时L.r是初始无序状态，TR为新申请的空数组，k=1，L.length=9。

2．第5～9行，循环的目的就两两归并，因s=1，n-2×s＋1=8，为什么循环i从1到8，而不是9呢？就是因为两两归并，最终9条记录定会剩下来，无法归并。

3．第7行，Merge函数我们前面已经详细讲过，此时i=1，i＋s-1=1，i＋2×s-1=2。也就是说，我们将SR（即L.r）中的第一个和第二个记录归并到TR中，然后第8行，i=i＋2×s=3，再循环，我们就是将第三个和第四个记录归并到TR中，一直到第七和第八个记录完成归并，如图9-8-14所示。

9.8.3　非递归实现归并排序 - 图4

图9-8-14

4．第10～14行，主要是处理最后的尾数，第11行是说将最后剩下的多个记录归并到TR中。不过由于i=9，n-s＋1=9，因此执行第13～14行，将20放入到TR数组的最后，如图9-8-15所示。

9.8.3　非递归实现归并排序 - 图5

图9-8-15

5．再次调用MergePass时，s=2，第5～9行的循环，由第8行的i=i＋2×s可知，此时i就是以4为增量进行循环了，也就是说，是将两个有两个记录的有序序列进行归并为四个记录的有序序列。最终再将最后剩下的第九条记录“20”插入TR，如图9-8-16所示。

9.8.3　非递归实现归并排序 - 图6

图9-8-16

6．后面的类似，略。

非递归的迭代方法，避免了递归时深度为log2n的栈空间，空间只是用到申请归并临时用的TR数组，因此空间复杂度为O(n)，并且避免递归也在时间性能上有一定的提升，应该说，使用归并排序时，尽量考虑用非递归方法。