c++ - 在 C++ 中实现归并排序

Question

我研究过归并排序的理论，但对如何在 C++ 中实现它一无所知。我的问题是，合并排序以递归方式创建数组。但是在实现的时候，我们如何在运行时创建数组呢？或者对此的一般方法是什么？

谢谢。

Answer 1

回答这个问题:在运行时创建动态大小的数组是使用 std::vector<T> 完成的。 .理想情况下，您会使用其中一种来获得您的输入。如果没有，很容易转换它们。例如，您可以像这样创建两个数组:

template <typename T>
void merge_sort(std::vector<T>& array) {
    if (1 < array.size()) {
        std::vector<T> array1(array.begin(), array.begin() + array.size() / 2);
        merge_sort(array1);
        std::vector<T> array2(array.begin() + array.size() / 2, array.end());
        merge_sort(array2);
        merge(array, array1, array2);
    }
}

但是，分配动态数组相对较慢，通常应尽可能避免。对于合并排序，您只需对原始数组的子序列进行排序并就地合并它们。看来，std::inplace_merge()要求双向迭代器。