c++ - 递归合并排序算法实现

Question

我是算法新手。我尝试使用 std::vector 实现递归合并排序。但我被困住了。该代码不起作用。

我看过《算法导论》中的算法，Cormen/Leiserson/Rivest/Stein 第 3 版。我尝试实现的伪代码。

这里是我的合并函数:

void merge(std::vector<int>& vec, size_t vec_init, size_t vec_mid, size_t vec_size) {
  int leftLoop = 0;
  int rightLoop = 0;
  int vecLoop = 0;
  size_t mid = vec_mid - vec_init + 1;

  std::vector<int> Left_Vec(std::begin(vec), std::begin(vec) + mid);
  std::vector<int> Right_Vec(std::begin(vec) + mid, std::end(vec));

  for (size_t vecLoop = vec_init; vecLoop<vec_size; ++vecLoop) {
      vec[vecLoop] = (Left_Vec[leftLoop] <= Right_Vec[rightLoop]) ? Left_Vec[leftLoop++] : Right_Vec[rightLoop++];
  }
}

这是我的合并排序函数

void merge_sort(std::vector<int>& vec, size_t vec_init, size_t vec_size) {
    if (vec_init < vec_size) {
      size_t vec_mid = (vec_init + vec_size) / 2;
      merge_sort(vec, vec_init, vec_mid);
      merge_sort(vec, vec_mid + 1, vec_size);
      merge(vec, vec_init, vec_mid, vec_size);
   }
} 

当输入vec = {30,40,20,10}时，输出vec = {10, 10, 0, 20}:

int main() {
    auto data = std::vector{ 30, 40, 20, 10 };
    merge_sort(data, 0, data.size());
    for (auto e : data) std::cout << e << ", ";
    std::cout << '\n';
    // outputs 10, 10, 0, 20, 
}

我对算法或代码的错误在哪里？

Answer 1

有几个问题。这些更改将修复代码:

void merge(std::vector<int>& vec, size_t vec_start, size_t vec_mid, size_t vec_end) {
  size_t leftLoop = 0;
  size_t rightLoop = 0;
  size_t vecLoop = 0;
  // Not needed, much simpler if mid is relative to vec.begin()
  //size_t mid = vec_mid - vec_init + 1;

  // You didn't take vec_init and vec_size into account when calculating the ranges.
  std::vector<int> Left_Vec(std::begin(vec) + vec_start, std::begin(vec) + vec_mid);
  std::vector<int> Right_Vec(std::begin(vec) + vec_mid, std::begin(vec) + vec_end);

  // Values are not uniformly distributed in the left and right vec. You have to check for
  // running out of elements in any of them.
  for (/*size_t*/ vecLoop = vec_start; leftLoop < Left_Vec.size() && rightLoop < Right_Vec.size(); ++vecLoop) {
    //   ^~~~~ shadowed outer vecLoop  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    vec[vecLoop] = Left_Vec[leftLoop] <= Right_Vec[rightLoop] ? Left_Vec[leftLoop++] : Right_Vec[rightLoop++];
  }

  // Copy the rest of the values into vec.
  if (leftLoop == Left_Vec.size())
    std::copy(Right_Vec.begin() + rightLoop, Right_Vec.end(), vec.begin() + vecLoop);
  else
    std::copy(Left_Vec.begin() + leftLoop, Left_Vec.end(), vec.begin() + vecLoop);
}

void merge_sort(std::vector<int>& vec, size_t vec_start, size_t vec_end) {
  // Should only run the function if there are at least 2 elements, otherwise vec_mid
  // would be always at least vec_start + 1 and the recursion would never stop.
  if (vec_end - vec_start >= 2) {
    size_t vec_mid = (vec_start + vec_end) / 2;
    merge_sort(vec, vec_start, vec_mid);
    merge_sort(vec, vec_mid /* + 1 */, vec_end);
    //                         ^~~ + 1 here would skip an element
    merge(vec, vec_start, vec_mid, vec_end);
  }
}