递归归并排序参数类型不匹配问题求助

错误原因 #

你的代码中merge函数的第一个参数要求是int*（C风格数组指针），但在mergeSort里调用merge时传入的是vector<int>对象，两种类型无法直接转换，导致编译错误。

错误信息：

main.cpp: In function ‘void mergeSort(std::vector&, int, int)’:
main.cpp:21:25: error: cannot convert ‘std::vector’ to ‘int*’ for argument ‘1’ to ‘void merge(int*, int, int, int)’
merge(array, p, mid, r);

解决方案 #

不需要修改merge函数的定义，只需要在调用时将vector<int>转换为int*类型即可，有两种可靠的方式：

方式1：使用vector的data()成员函数（推荐） #

C++11及以后的标准中，vector提供了data()方法，直接返回指向内部存储数组的指针，类型匹配int*。

修改mergeSort中的调用语句：

merge(array.data(), p, mid, r);

方式2：取vector第一个元素的地址 #

如果编译器不支持C++11，可以使用&array[0]获取内部数组的指针（前提是vector不为空，而归并排序场景下数组必然非空）：

merge(&array[0], p, mid, r);

修改后的完整mergeSort函数 #

// Takes in an array and recursively merge sorts it
void mergeSort(vector<int>& array, int p, int r) {
  if(p >= r)
  {
    return;
  }
  int mid = (p + r) / 2;
  mergeSort(array, p, mid);
  mergeSort(array, mid + 1, r);
  merge(array.data(), p, mid, r); // 这里完成类型转换
};

内容的提问来源于stack exchange，提问作者Heston Vaughan