中位数排序的真实名称是什么？我在哪里可以找到更多相关材料？

Question

我正在阅读由O'Reilly Media出版的《算法简介》一书，其中有一节讲述排序算法，其中提到了一种叫做中位数排序（Median Sort）的算法。由于我之前从未听说过这个算法，而我的CS3课本（涵盖了算法）中也没有列出它，因此我在谷歌上搜索并尝试在维基百科上查找，但都没有找到相关信息。如果有人能提供一个易于查找该算法的名称或指向其他相关资源，我将不胜感激。谢谢。

此外，根据我对该算法的理解，它本质上是快速排序（Quicksort），只是它总是使用中位数作为枢轴。所谓中位数，似乎是扫描项数组并选择中间值作为枢轴，而不是选择数组中间项作为枢轴。此外，该书还提到了Blum-Floyd-Pratt-Rivest-Tarjan（BFPRT）与“中位数”排序有关。

- mnuzzo

Answer 1

由于我没有上述的书，我会猜测 Blum-Floyd-Pratt-Rivest-Tarjan 算法（如果您想了解更多，请参阅 论文）可能用于选择枢轴。我还建议您阅读同一维基百科文章中的基于分区的通用选择算法部分，因为我认为这正是您要寻找的内容。

- user11617

Answer 2

大多数快速排序的版本选择三个元素的中位数（通常是第一个，中间和最后一个），这通常被称为中位数3快速排序。只是以中间元素作为枢轴通常不符合任何名称，除了快速排序。

编辑（很久以后，在看到问题中的编辑之后）：看起来你所说的是使用“中位数中位数”算法选择QuickSort的枢轴元素。中位数中位数算法更为人所知的是独立地用作Hoare的Select算法的替代方法（或改进方法，取决于您的观点）。这被认为可以在线性时间内找到中位数（或其他等级，但在这种情况下，我们只关心中位数）。

底线是，排序仍然是快速排序。 Hoare选择枢轴元素的描述既不需要也不禁止选择中位数中位数选择：

引用： “分区过程的第一步是选择一个特定的键值，该键值已知在要排序的段的项目的键范围内。确保这一点的简单方法是选择段中某个项目的实际键值。所选择的键值将被称为 bound 。“

当然，现在几乎每个人都称其为“枢轴”，而不是“界限”，但这基本上是无关紧要的。用于选择枢轴/界限的方法是开放的。

- Jerry Coffin

---

快速排序本质上是一种更简单的中位数排序，所以你部分正确。然而，这些是不同的算法。 - user11617

@RobertD.：是的，他在我回答一个小时后进行了编辑，很明显他不仅仅是在谈论快速排序——但当我写下这个答案时，这一点并不清楚。因为问题有缺陷而对答案进行负评。万岁！ - Jerry Coffin

由于我目前没有超能力，所以我不可能知道我是因为问题的缺陷而“下投票”了答案。但是，我已经修复了错误。 - user11617

@RobertD.：如果您查看问题底部的“编辑于Aug 23 '10 at 5:12”处，该日期/时间部分是一个超链接，可以让您查看问题的编辑历史记录。如果您查看我的原始答案的日期/时间，您会发现它在编辑之前发布的。 - Jerry Coffin

Answer 3

我没有这本书，但我猜测书中提到的算法是Floyd-Rivest's SELECT算法。Blum-Floyd-Pratt-Rivest-Tarjan（BFPRT）是指他们在这篇论文中讨论早期的PICK（现在被称为Median of medians）选择算法：

M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan，“Time Bounds for Selection,” Journ. Comp. and. Sys. Sci.，vol. 7，iss. 4，pp. 448-461，1973。

这篇论文建立了计算机科学中选择问题的早期理解。

- Jaime Martinez

Answer 4

是的，你说得对，它与快速排序类似，但它比快速排序更好的地方在于它避免了那些数组被分割得非常不均匀（不是等分）的情况。 因为在快速排序中，我们无法确定每次数组是否会被分成两个相等或近乎相等的部分。在中位数排序中，我们通过付出找到中位数的代价来确保这一点，但这可能值得让快速排序类似于归并排序，并且具有原地排序的好处。

- Aditya Maheshwari