时间戳

首页 > 解决方案 > 如何在 C++ 中为 mergeSort 编写合并函数？

c++ - 如何在 C++ 中为 mergeSort 编写合并函数？

问题描述

我正在学习 C++ 并尝试编写合并函数，该函数将采用两个排序列表并将它们组合成一个排序列表。这应该在 O(n) 时间内运行。下面是我的代码：

LinkedList<T> LinkedList<T>::merge(const LinkedList<T>& other) const {

  LinkedList<T> left = *this;
  LinkedList<T> right = other;

  LinkedList<T> merged;

  if (left.size() <= 1) {
    return left;
  }
  else{
    while (left.size() > 0 && right.size() > 0){

          if (left.front() <= right.front()){
            merged.pushBack(left.front());
            left.popFront();
          }
          else {
            merged.pushBack(right.front());
            right.popFront();
          }
      }
  }

  return merged;
}

这是我的测试：

Testing merge():
Left List: [(1)(3)(5)]  Right List: [(-1)(2)(10)(20)]
Merged: [(-1)(1)(2)(3)(5)]
Expected: [(-1)(1)(2)(3)(5)(10)(20)]

我认为这是因为当其中一个列表为空时，循环停止。谁能建议我如何处理这个问题？非常感谢。

标签： c++data-structureslinked-list

解决方案

在有条件运行的主 while 循环之后，直到两个数组都包含元素。因此，当其中一个为空时，它会退出，并且其中一个数组可能仍包含剩余的元素。您还需要在外部添加一个 while 循环，以将剩余的元素添加到结果数组中。这是示例：

while (left.size() > 0)
{
            merged.pushBack(left.front());
            left.popFront();
}
while (right.size() > 0)
{
            merged.pushBack(right.front());
            right.popFront();
}

推荐阅读