时间戳

首页 > 解决方案 > 无法理解如何递归合并排序

c++11 - 无法理解如何递归合并排序

问题描述

目前通过 Daniel Liang 的 Introduction to C++ 自学 C++。

关于合并排序的话题，我似乎无法理解他的代码是如何递归调用自身的。

我了解合并排序的一般概念，但我无法具体理解此代码。

在此示例中，我们首先将列表 1、7、3、4、9、3、3、1、2 及其大小 (9) 传递给 mergeSort 函数。从那里，我们将列表分成两部分，直到数组大小达到 1。在这种情况下，我们将得到：1,7,3,4 -> 1,7 -> 1。然后我们进入合并排序的后半部分. 在这种情况下，后半数组将是 7。我们合并两个数组 [1] 和 [7] 并继续删除动态分配的两个数组以防止任何内存泄漏。

我不明白的部分是这段代码是如何从这里运行的？在 delete[] firstHalf 和 delete[] secondHalf 之后。根据我的理解，不应该有另一个mergeSort函数调用来对新的firstHalf和secondHalf进行合并排序吗？

#include <iostream>
using namespace std;

// Function prototype
void arraycopy(int source[], int sourceStartIndex,
  int target[], int targetStartIndex, int length);

void merge(int list1[], int list1Size,
  int list2[], int list2Size, int temp[]);

// The function for sorting the numbers 
void mergeSort(int list[], int arraySize)
{
  if (arraySize > 1)
  {
    // Merge sort the first half
    int* firstHalf = new int[arraySize / 2];
    arraycopy(list, 0, firstHalf, 0, arraySize / 2);
    mergeSort(firstHalf, arraySize / 2);

    // Merge sort the second half
    int secondHalfLength = arraySize - arraySize / 2;
    int* secondHalf = new int[secondHalfLength];
    arraycopy(list, arraySize / 2, secondHalf, 0, secondHalfLength);
    mergeSort(secondHalf, secondHalfLength);

    // Merge firstHalf with secondHalf
    merge(firstHalf, arraySize / 2, secondHalf, secondHalfLength,
      list);

    delete [] firstHalf;
    delete [] secondHalf;
  }
}

void merge(int list1[], int list1Size,
  int list2[], int list2Size, int temp[])
{
  int current1 = 0; // Current index in list1
  int current2 = 0; // Current index in list2
  int current3 = 0; // Current index in temp

  while (current1 < list1Size && current2 < list2Size)
  {
    if (list1[current1] < list2[current2])
      temp[current3++] = list1[current1++];
    else
      temp[current3++] = list2[current2++];
  }

  while (current1 < list1Size)
    temp[current3++] = list1[current1++];

  while (current2 < list2Size)
    temp[current3++] = list2[current2++];
}

void arraycopy(int source[], int sourceStartIndex,
  int target[], int targetStartIndex, int length)
{
  for (int i = 0; i < length; i++)
  {
    target[i + targetStartIndex] = source[i + sourceStartIndex];
  }
}

int main()
{
  const int SIZE = 9;
  int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2};
  mergeSort(list, SIZE);
  for (int i = 0; i < SIZE; i++)
    cout << list[i] << " ";

  return 0;
}

标签： c++11mergesort

解决方案

根据我的理解，不应该有另一个mergeSort函数调用来对新的firstHalf和secondHalf进行合并排序吗？

它在递归调用期间隐式发生。当您到达这两行时：

delete [] firstHalf;
delete [] secondHalf;

这意味着一次调用mergeSort已完成。如果此调用属于合并前半部分，则代码从后面的行开始，即这些行：

// Merge sort the second half
int secondHalfLength = arraySize - arraySize / 2;
...

但是，如果此调用属于后半部分的合并，则控制返回到该调用之后的行，即这些行：

// Merge firstHalf with secondHalf
merge(firstHalf, arraySize / 2, secondHalf, secondHalfLength,
  list);

如果一切都按计划进行。

推荐阅读