algorithm - 将列表分成 2 个相等的部分

Question

我有一个包含随机数的列表，使得 Number >= 0。现在我必须将列表分成 2 个相等的部分(假设列表包含偶数个元素)，这样第一个列表中包含的所有数字都小于第二个列表中的数字。这可以通过 O(nlogn) 中的任何排序机制轻松完成。但我不需要在任何两个等长列表中对数据进行排序。唯一的条件是(第一个列表中的所有元素 <= 第二个列表中的所有元素。)那么有没有一种方法或技巧可以降低复杂性，因为我们在这里不需要排序的数据？

Answer 1

如果问题实际上可以解决(数据正确)，您可以使用 selection algorithm 找到中位数.当你拥有它时，你只需创建 2 个大小相等的数组并逐个元素迭代原始列表元素，将每个元素放入任一新列表中，具体取决于它是大于还是小于中位数。应该以线性时间运行。

@Edit:正如 gen-y-s 指出的那样，如果您自己编写选择算法或使用适当的库，它可能已经划分了输入列表，因此不需要第二遍。