在不排序的情况下查找未排序数组的中位数

Question

有没有一种方法可以找到未排序数组的中位数： 1- 不用排序。 2- 不使用选择算法或中位数算法。

我发现很多类似于我的问题。但是其中大部分解决方案都讨论了SelectProblem和MedianOfMedians算法。

- Monica

---

@GordonLinoff 在问题中提到了 Hoare 算法（“不使用选择算法”）。 - ig-melnyk

为什么会有任意的限制？你们尝试过什么方法？ - SirGuy

@GordonLinoff：我记得在SO上看到过一个不错的答案，它使用了两个堆，并在值添加到任一侧时将它们保持相等的大小。我在其他问题的几个答案中也见过这种情况，但我找不到像我记得的那个一样的答案。我认为它看起来相当高效，并且有一些技巧可以从一个堆中删除元素并添加到另一个堆中以重新平衡（如果必要）。嗯。 - Peter Cordes

如果有一种有效的方法来做到这一点，那么由于数据的中位数是Quicksort的理想枢轴，它将使Quicksort变得更好。 - Abhishek Choudhary

@SirGuy 如果您有一个数据集太大而无法一次性加载到内存中，那么对其进行排序可能是不可行的。而且，中位数算法并不一定会得出中位数，所以仅仅使用它也不会起作用。但是，当谈到数组时，它无疑似乎已经在RAM中了。 - undefined

Answer 1

你可以在不对数组进行排序的情况下找到中位数。但是高效地执行此操作并不容易。

例如，你可以遍历数组的每个元素; 对于每个元素，计算小于等于它的元素数量，直到找到具有正确计数的值为止。这将需要O(n²)时间，但只需要O(1)空间。

或者，你可以使用一个最小堆，其大小略大于数组大小的一半。（也就是说，如果数组有2k或2k+1个元素，则堆应该有k+1个元素）。使用第一个数组元素构建堆，使用标准堆构建算法（O(N)）构建堆。然后，对于每个剩余的元素x，如果x大于堆的最小值，则用x替换最小元素并执行SiftUp操作（O(log N)）。最后，中位数要么是堆的最小元素（如果原始数组大小为奇数），要么是堆中两个最小元素的平均值。所以总时间复杂度为O(n log n)，如果你不能重新排列数组元素，则空间复杂度为O(n)。（如果你可以重排数组元素，则可以原地执行此操作。）

- rici

---

如果数组的大小是奇数怎么办？另外，当你说“如果x大于堆的最小值，则用x替换最小元素”，我是否还需要平衡minHeap，因为替换后树不再是minHeap。 - CocoCrisp

我不太理解它的工作原理，但对于奇数和偶数大小的数组，它对我有效。我想请求一个解释或关于“这是如何工作”的参考！ - CocoCrisp

@Milind：编辑了答案，更加准确地讲述了奇偶数组大小的问题。是的，在交换之后你必须执行SiftUp操作，但这很快。 - rici

Answer 2

有一种随机算法可以在 O(n) 步骤内完成此任务（平均情况），但它确实涉及对数组的某些子集进行排序。并且，由于其随机性质，无法保证它会真正完成（尽管这种不幸的事件应该以消失的概率发生）。

我将在此留下主要思想。有关更详细的说明以及为什么此算法有效的证明，请查看此处。

设A为您的数组，令n=|A|。假设所有A的元素都是不同的。算法步骤如下：

1. 从 A 中随机选择 t = n^(3/4) 个元素。
2. 令 T 为所选元素的“集合”。对 T 进行排序。
3. 设置 pl = T[t/2-sqrt(n)] 和 pr = T[t/2+sqrt(n)]。
4. 遍历 A 的元素，并确定有多少个元素小于 pl（用 l 表示），有多少个元素大于 pr（用 r 表示）。如果 l > n/2 或者 r > n/2，返回到步骤 1。
5. 让 M 成为在 pl 和 pr 之间的 A 的元素集合。如果我们到达步骤 5，则可以在步骤 4 中确定 M 的大小是否不超过 4t，并对其进行排序。否则，返回到步骤 1。
6. 将 m = M[n/2-l] 作为中位数元素返回。

算法的主要思想是获取两个元素（pl 和 pr），这两个元素包含中位数元素（即 pl < m < pr），并且在数组的有序版本中这两个元素非常接近（而不需要实际对数组进行排序）。高概率情况下，所有六个步骤只需要执行一次（也就是说，你将从第一次通过步骤1-5获得具有这些“好”属性的pl和pr，因此不需要返回到步骤1）。一旦找到这样的两个元素，您可以简单地对它们之间的元素进行排序，并找到A的中位数元素。

第二步和第五步确实涉及一些排序（这可能违反了您神秘地建立的“规则” :p）。如果对子数组进行排序是可行的，您应该使用某种在O(slogs)步骤中完成此操作的排序方法，其中s是要排序的数组的大小。由于T和M显着小于A，因此排序步骤需要“少于”O(n)步骤。如果对于排序子数组也违反规则，则应考虑到在两种情况下都不真正需要排序。您只需要找到一种确定pl、pr和m的方法，这只是另一个选择问题（具有相应的索引）。虽然对T和M进行排序可以实现这一点，但您可以使用任何其他选择方法（也许是rici之前建议的方法）。

- cobarzan

Answer 3

描述了一种非破坏性例程selip()，详见http://www.aip.de/groups/soe/local/numres/bookfpdf/f8-5.pdf。该程序通过多次遍历数据，在每个阶段内在当前值范围内随机选择项目，然后计算项目数量以确定随机选择的排名。

- mcdowella