我正在阅读O'Reilly Media出版的《坚果中的算法》一书，正在阅读有关排序算法的部分，发现其中一本叫做“中值排序”。由于我以前从未听说过它，而且CS3的教科书(涵盖算法)没有列出，因此我在google上搜索并尝试在Wikipedia上查找它，但未发现任何内容。如果有人可以提供名称，我可以很容易地在其下查找该算法或将其指向其他有关它的资源，我将不胜感激。谢谢你。
另外，据我所知，该算法本质上是Quicksort，只是它始终使用中位数作为枢轴。以中值表示，我的意思是似乎要扫描项目数组并将中间值作为枢轴，而不是选择数组中的中间项目作为枢轴。此外，该书还提到了与“中位数”排序有关的Blum-Floyd-Pratt-Rivest-Tarjan(BFPRT)。
最佳答案
快速排序的大多数版本会选择(例如)三个元素的中位数(通常是第一个，中间和最后一个)，通常会提供3个快速排序的中位数。仅仅从中间元素开始作为枢轴，除了Quicksort之外，通常不符合其他任何名称的条件。
编辑(很久以后，在看到问题中的编辑之后):您似乎在说的是使用“中位数中位数”算法选择QuickSort的枢轴元素。中位数的中位数算法因独立地用作Hoare's Select算法的替代方案(或根据您的观点进行细化)而广为人知。可以找到线性时间中的中位数(或其他等级，但在这种情况下，我们只关心中位数)是众所周知的。
最重要的是，排序实际上仍然是Quicksort。 Hoare对选择枢轴元素的描述既不需要也不禁止选择中位数:
当然，现在几乎每个人都将其称为“枢轴”，而不是“约束”，但这几乎是无关紧要的。选择枢轴/装订的方法保持打开状态。
关于algorithm - 中位数排序的真实名称是什么，和/或在哪里可以找到更多 Material ？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3544639/