c++ - 对由排序数组组成的合并数组进行排序

Question

我有两个排序数组，例如(3,4,5) 和 (1,3,7,8)，我得到了组合排序数组 (3,4,5,1,3,7,8)。

现在我想对已经组合的数组进行排序，而不是拆分它，而是通过覆盖它，利用它由 2 个已经排序的数组组成的事实。有什么办法可以有效地做到这一点？我知道有很多关于如何通过迭代排序数组然后将值相应地放入新数组来执行此操作的线程，但我还没有在任何地方看到这种类型的问题。我想在 c 中执行此操作，但非常感谢任何帮助/伪代码。谢谢!

编辑:将进行排序的函数将只给出组合数组和(可能)其他两个数组的长度(如果需要)。

Answer 1

如果您已经拥有原始排序数组，则组合数组(注意它未排序)并没有真正帮助，除非您的目标存储已经分配。

有一个众所周知且非常简单的算法用于合并两个已排序的范围，但您可以只使用 std::merge而不是自己编写代码。

请注意，仅适用于非重叠 输入和输出范围:对于您修改后的问题，请使用 std::inplace_merge ，中间迭代器设置为第二个序列中的第一个元素:

void sort_combined(int *array, size_t total, size_t first) {
    std::inplace_merge(array, array + first, array + total);
}

// and use it like

int combined[] = {3, 4, 5, 1, 3, 7, 8};
const size_t first = 3;
const size_t second = 4;
const size_t total = 7; // == sizeof(combined)/sizeof(*combined)

sort_combined(combined, total, first);