问题标签 [median-of-medians]

我正在使用中位数算法进行快速排序。我通常使用选择排序来获得 5 个元素的子数组的中位数。但是，如果有数千个子数组，则意味着我必须找到千位中位数的中位数。我想我不能使用选择排序来找到那个中位数，因为它不是最优的。

问题：

谁能建议我找到中位数的更好方法？提前致谢。

在实现对快速排序分区的改进时，我尝试使用 Tukey 的 ninther 来找到枢轴（几乎从 sedgewick 在QuickX.java中的实现中借用了所有内容）

每次对整数数组进行洗牌时，下面的代码都会给出不同的结果。

tukey's ninther 会为同一数据集的不同改组提供不同的值吗？当我试图手动找到中位数的中位数时，我发现代码中的上述计算是正确的。这意味着同一个数据集产生的结果与数据集的中位数不同。这是正确的行为吗？有更多统计知识的人可以发表评论吗？

我必须将数组的元素分成 3 组。这需要在不对数组进行排序的情况下完成。考虑这个例子

我们有 120 个未排序的值，因此最小的 40 个值需要在第一组中，接下来的 40 个在第二组中，最大的 40 个在第三组中

我正在考虑中位数方法的中位数，但无法将其应用于我的问题，请建议一种算法。

我试图理解寻找中位数的选择算法。我在下面粘贴了伪代码。

我有一个非常琐碎的疑问。我想知道作者上面写的 i<=25 的蛮力是什么意思。是不是他会一个一个地比较元素和其他元素，看看它是第k大的还是别的。

我一直试图了解“5”在Median of Medians 算法中的来源，但似乎无法找到一个简单的描述来说明它是如何派生的以及为什么它是最优的。

例如，为什么说 7 不是一个可行的选择？

我可以看到 5 的唯一优势是它在中间的每一侧都有 2 个项目，这使得对 5 个项目的排序成为不超过 3 次交换的简单案例。

我试图更好地理解减少，我目前正在研究两种算法，“中位数的中位数”和快速排序。

我知道这两种算法都使用相似（实际上相同）的分区子例程来帮助解决它们的问题，最终使它们非常相似。

那么对于这两种算法，“减少”一词是否有意义？以下任何一项有意义吗？

• Medians/Quicksort 的中值可以简化为一个分区子程序

• 中位数的中位数减少到快速排序

• 快速排序减少到中位数的中位数

我在 github 中找到了此代码，用于quickselect算法，也称为order-statistics. 这段代码工作正常。

我不明白medianOf3方法，它应该按排序顺序排列第一个、中间和最后一个索引。medianof3但实际上在调用方法后输出数组时并没有。除了最后一次调用swap(list, centerIndex, rightIndex - 1);. 有人可以解释为什么会这样吗？

我试图了解分布式计算，但遇到了一个寻找大量数字中位数的问题：

假设我们有大量无法放入内存（大小为 N）的数字（假设元素数量为 N*K）。我们如何找到这些数据的中位数？假设在内存上执行的操作是独立的，即我们可以认为有 K 台机器，每台机器最多可以处理 N 个元素。

我认为中位数的中位数可以用于此目的。我们可以一次将 N 个数字加载到内存中。我们及时找到该集合的中位数O(logN)并将其保存。

然后我们保存所有这些 K 个中位数并找出中位数的中位数。再次O(logK)，到目前为止的复杂性O(K*logN + logK)。

但是这个中位数只是一个近似的中位数。我认为将它用作获得最佳案例性能的支点将是最佳选择，但为此我们需要将所有 N*K 数字放入内存中。

既然我们有一个很好的近似枢轴，我们如何才能找到集合的实际中位数？

您好，我想了解中位数算法的中位数是如何工作的。到目前为止，在我看到的所有示例中，在算法开始执行之前，就已经存在被划分的数字组。所以我无法理解这些组是如何组成的。更具体地说，在目前研究的示例中，声明有 9 组，每组 5 个数字，例如 45 个数字，或 4 组 10 个数字，也就是 40 个数字。那么如果我们有n个数字怎么办？我应该遵循什么好的技术来找到它的组应该有的元素数量？

我想在未排序列表中找到近似中位数，我知道两种算法

算法1-快速选择

算法 2- 中位数的中位数

我不能在我的项目中使用快速选择，因为在最坏的情况下它需要 O(n^2)。我听说过中位数的中位数，但我的同事建议它需要 O(n) 和一些常数因子。因此它的时间复杂度是 Cn 并且常数因子与快速选择相比很大。我想知道与中位数的中位数相关的常数因子是什么？为什么中位数的中位数不使用 9 元素的伪中位数？
或者他们是否有任何其他算法可以在线性时间 O(n) 中找到近似中位数？