排序合并数组组成的排序阵列

我有两个排序的数组，例如（3,4,5）和（1,3,7,8），我得到了组合的排序数组（3,4,5,1,3,7,8）。排序合并数组组成的排序阵列

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

编辑：将执行排序的函数只会给出组合数组和（如果需要的话）其他两个数组的长度（可能）。

来源

2016-11-16 SoflolikeAntonio

相反支出有很多时间对已经合并的数组进行排序，那么改变当前抛出两个数组到单个数组中的代码是不是会容易得多？你知道，那个代码可以简单地进行合并，同时建立新的数组？而不是先将两个数组合并成一个，然后计算如何有效地重新排序。 – GhostCat

我不明白你的意思。你的意思是覆盖和不吐口水？为什么标准的快速或预先分类将不适用于您的情况？ – Sigstop

@Sigstop我想他想说：我有一个数组，它由两个有序数字序列组成。有没有一种方法根据这种知识对数组进行排序......没有做出“真正的”排序;并且不会创建另一个新阵列。 – GhostCat

如果你已经有原始的排序阵列，组合阵列（注意它是而不是排序）没有真正的帮助，除了你的目标存储已分配。

有一个众所周知的，非常简单的算法来合并两个排序的范围，但您可以使用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);

来源

2016-11-16 13:30:52 Useless

排序合并数组组成的排序阵列

回答

相关问题