将列表分成两个相等的部分。

Question

我有一个包含随机数字的列表，数字 >= 0。现在，我需要将该列表分成两个相等的部分（假设列表包含偶数个元素），使得第一个列表中包含的所有数字都小于第二个列表中存在的数字。这可以通过任何排序机制在O(nlogn)时间内轻松完成。但是我不需要数据在两个等长的列表中排序。唯一的条件是：（第一个列表中的所有元素 <= 第二个列表中的所有元素。） 那么，既然我们不需要排序数据，是否有什么方法或技巧可以降低复杂性呢？

- Neer1009

---

你所描述的是快速排序的基础，我猜问题就源于此。你需要找到一个中位数，然后根据它来进行操作。请参考https://en.wikipedia.org/wiki/Quicksort。 - Robert Goldwein

请参见http://cs.stackexchange.com/questions/1914/to-find-the-median-of-an-unsorted-array。 - Lior Kogan

谢谢Robert，我有一个解决它的想法。 - Neer1009

Answer 1

如果问题实际上是可以解决的（数据正确），您可以使用选择算法找到中位数。当您拥有它时，只需创建两个大小相等的数组，并逐个迭代原始列表元素，将每个元素放入其中一个新列表，具体取决于它是大于还是小于中位数。应该在线性时间内运行。

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

- Mateusz Dymczyk

---

正确，除了选择算法已经将数组分成两部分，一部分小于中位数，一部分大于中位数。 - gen-y-s

@gen-y-s 发现得非常好，有些方法只返回“中位数”，所以这取决于你是自己编写还是使用第三方。 - Mateusz Dymczyk

@MateuszDymczyk .. 你能列出一些可以直接返回中位数的方法吗？ - Neer1009

@Neer1009 我认为Apache Commons Math有一个Median类，使用选择算法来计算。你也可以看看Java中的SSJ（随机模拟）。 - Mateusz Dymczyk