c++ - 如何使用 C++ 有效地将排序与 vector 合并

Question

我通过使用 vector 作为函数在 C++ 中实现了合并排序参数而不是索引(开始，结束)。但是，我很想知道这样做在速度方面是否有任何折衷和空间复杂度

代码:

void mergeSort(std::vector<int> &array) {
    if(array.size() == 1) return;
    else {
      const unsigned int len = array.size();
      const int lo = floor((double)len/2);
      const int hi = ceil((double)len/2);

      std::vector<int> L(&array[0], &array[lo]);
      std::vector<int> R(&array[lo], &array[len]);

      mergeSort(L);
      mergeSort(R);
      merge(array, L, R);
    }
    return;
}

每次调用合并排序都创建新列表可能不是可行的方法，但这就是合并排序功能的工作原理。此外，速度有多快/慢:

std::vector<int> L(&array[0], &array[lo]);

合并函数如下所示:

void merge(
           std::vector<int> &array, 
           std::vector<int> &L, 
           std::vector<int> &R
          ) {
    std::vector<int>::iterator a = array.begin();
    std::vector<int>::iterator l = L.begin();
    std::vector<int>::iterator r = R.begin();

    while(l != L.end() && r != R.end()) {
      if (*l <= *r) {
      *a = *l;
      l++;
      }
      else {
        *a = *r;
        r++;
      }
      a++;
   }
   while (l != L.end()) {
     *a = *l;
     a++;
     l++;
   }
   while (r != R.end()) {
     *a = *r;
     a++;
     r++;
   }
   return;

Answer 1

好吧，不需要在每次调用 merge 时创建新空间。 std::vector<int> L(&array[0], &array[lo]);实际上会创造空间来容纳lo元素并将执行 lo也复印件。

你永远不会使用更多 O(n)用于存储值的额外空间。那么，为什么不分配一个足够大的缓冲区来容纳预先复制整个 vector 并使每个递归调用对数据的特定部分进行操作？这样您就不必在每次调用时都创建新的 vector 。

另外，我也会鼓励你制作 mergesort适用于迭代器而不是 vector<int>仅有的。像下面这样的界面应该就足够了。

template < typename Iterator, typename Compare>
void mergesort(Iterator s, Iterator e, Compare cmp);

On Github你可以找到我刚才实现的合并排序版本。我想这应该足够了。