C++ 如何 MergeSort 什么都不返回但工作正常？

Question

下面就是归并排序的实现。但是，我什至不明白这段代码是如何工作的。我们不使用指针，

main()

中没有返回任何内容。那么，它是如何操纵

myarray

的呢？谁能解释一下？

代码如下：

#include < iostream >
using namespace std;

void merge(int arr[], int l, int m, int r) {
  int i = l;
  int j = m + 1;
  int k = l;

  /* create temp array */
  int temp[5];

  while (i <= m && j <= r) {
    if (arr[i] <= arr[j]) {
      temp[k] = arr[i];
      i++;
      k++;
    } else {
      temp[k] = arr[j];
      j++;
      k++;
    }

  }

  /* Copy the remaining elements of first half, if there are any */
  while (i <= m) {
    temp[k] = arr[i];
    i++;
    k++;

  }

  /* Copy the remaining elements of second half, if there are any */
  while (j <= r) {
    temp[k] = arr[j];
    j++;
    k++;
  }

  /* Copy the temp array to original array */
  for (int p = l; p <= r; p++) {
    arr[p] = temp[p];
  }
}

合并排序函数：

/* l is for left index and r is right index of the 
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    // find midpoint
    int m = (l + r) / 2;

    // recurcive mergesort first and second halves 
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    // merge
    merge(arr, l, m, r);
  }
}

主要功能：

int main() {
  int myarray[5];
  //int arr_size = sizeof(myarray)/sizeof(myarray[0]);
  int arr_size = 5;

  cout << "Enter 5 integers in any order: " << endl;
  for (int i = 0; i < 5; i++) {
    cin >> myarray[i];
  }
  cout << "Before Sorting" << endl;
  for (int i = 0; i < 5; i++) {
    cout << myarray[i] << " ";
  }
  cout << endl;
  mergeSort(myarray, 0, (arr_size - 1)); // mergesort(arr,left,right) called

  cout << "After Sorting" << endl;
  for (int i = 0; i < 5; i++) {
    cout << myarray[i] << " ";
  }

  return 0;
}

Answer 1

这个程序使用了从 C 获得的 C++ 的两个模糊特性以实现向后兼容性。

1. 数组到指针的衰减。在大多数情况下，提及数组名称实际上是获取数组第一个元素地址的简写。因此，

   mergeSort(myarray, ...)

   与

   mergeSort(&myarray[0], ...)

   相同。
2. 函数参数类型调整。您不能按值将数组传递给函数，那么

   void mergeSort(int arr[], ...)

   是什么意思？就像在 C 中一样，类型为 array-of-something 的函数参数被调整为 pointer-to-something。所以这个函数和

   void mergeSort(int* arr, ...)

完全一样

所以这个程序毕竟使用了指针，它们只是被薄薄地掩盖了。

上面提到的特性对于处理C风格的数组是必不可少的。 C++ 有 C 风格数组的替代方案，即

std::array

和

std::vector

，在大多数情况下通常推荐使用它们。