c++ - C++ 中的递归合并排序示例

Question

我有一个关于 C++ 递归的非常普遍的问题。为了更好地理解，我使用以下合并排序示例来解释我的不确定性。

   void mergesort (int* first, int* last)
{
   int n = last - first;
   if (n<=1)return;
   int* middle = first + n/2;
   mergesort (first, middle);
   mergesort (middle, last);
   merge (first,middle, last);
}

必须定义函数merge的位置。函数参数int*first,int*last分别是指向数组中第一个和最后一个元素的指针。假设数组的长度为 10。让我们看看会发生什么:

1. 由于 10 大于 1，因此我们声明一个指针 int* middle = first + 5;。

现在我的问题是:我们正在调用mergesort(first, middle)，一旦我们将数组的第一个元素分割成单个“元素”，这个递归就会结束。但是 mergesort(middle,last) 是在 mergesort(first,middle) 终止后执行还是同时执行？不知何故，它必须是同时的，否则我们不会将后半部分分成单个“元素”。上次的合并排序也有同样的问题。那么递归是如何执行多个函数调用的呢？

编辑我添加了完整的源代码以及输出:

//Mergesort.cpp
//

#include <iostream>
void merge (int* first, int* middle, int* last)
{
  int n = last - first;
  std::cout<<"merge part, n= " << n<<"\n";
  std::cout<<"merge part, middle= " << *middle << "\n";
  std::cout<<"merge part, last= "<<*last << "\n";
  int* deck = new int[n];

  int* left = first;
  std::cout<<"merge part, left = first " << *left<< "\n";
  int* right = middle;
  std::cout << "merge part, right = middle " << *right << "\n";
  for (int* d = deck; d!=deck+n;++d){
    if (left == middle) *d = *right++;
    else if (right==last ) *d=*left++;
    else if (*left < *right) *d = *left++;
    else *d = *right++;}

  int *d = deck;
  while (first != middle) *first++ = *d++;
  while (middle != last) *middle++ = *d++;

  delete[] deck;
}


void mergesort (int* first, int* last)
{
  int n = last - first;
  if (n <= 1) return;
  std::cout << "n= " << n;
  int* middle = first + n/2;
  std::cout << "first = "<< *first << "middle = "<< *middle<<"\n";
  mergesort (first, middle);
  mergesort (middle, last);
  merge (first, middle, last);
}

int main () 
{
  int a[4]={6,2,1,3};
  int* first = a;
  int* last = a+4;
  mergesort (first, last);
  std::cout<< a[0]<< a[1]<< a[2]<< a[3]<<"\n";
  return 0;
}

输出:

ThinkStation-S20:~/c++/test_files$ ./mergesort 
n= 4first = 6middle = 1
n= 2first = 6middle = 2
merge part, n= 2
merge part, middle= 2
merge part, last= 1
merge part, left = first 6
merge part, right = middle 2
n= 2first = 1middle = 3
merge part, n= 2
merge part, middle= 3
merge part, last= 4197792
merge part, left = first 1
merge part, right = middle 3
merge part, n= 4
merge part, middle= 1
merge part, last= 4197792
merge part, left = first 2
merge part, right = middle 1
1236

Answer 1

C++ 与 C 一样，按顺序执行语句，一个接一个。因此，对归并排序的第二次调用将在第一个调用返回后发生。通过适当的合并定义，就可以很好地工作。我强烈建议您亲自尝试该程序，用纸和铅笔模拟计算机。这不会花你太长时间(老实说!)，它应该会解决你的疑虑。

与快速排序一样，合并排序可以(部分)并行执行。对归并排序的两个递归调用彼此独立，因此执行可能会重叠。但如果没有相当多的额外工作，C++ 不会为您做到这一点。

---

这是用铅笔和纸完成此操作的一种方法，我认为这比尝试解释 printf 输出更容易理解。

1. 制作大约十二张卡片大小的纸张。
2. 从 main 第一次调用归并排序开始。
3. 抓取其中一张卡片，并填写四个变量:第一个、最后一个、中间、n。
4. 逐步执行合并排序行，直到到达新的调用。在当前卡上写入调用的行号，将其放入“堆栈”(开始时为空)，然后继续步骤 3。
5. 当你到达归并排序的末尾时，丢弃当前的卡片并返回到前一张卡片，该卡片将位于堆栈的顶部。继续执行步骤 4，从合并排序的下一行开始。
6. 完成所有开始的卡片后，您就完成了。