我正在阅读O'Reilly Media出版的"坚果壳中的算法"一书,我正在阅读有关排序算法的部分,并找到了一个名为Median Sort的部分.由于我之前从未听说过它,而且我的CS3教科书(其中涵盖的算法)没有列出,我搜索了它并尝试在维基百科上查找并没有发现任何内容.如果有人可以提供我可以轻松查看算法的名称或者指向其他有关它的资源,我将不胜感激.谢谢.
另外,从我能说的算法来看,它基本上是Quicksort,除了它总是使用中值作为枢轴.通过中值我的意思是它似乎扫描项目数组并选择中间值作为枢轴,而不是选择数组中的中间项作为枢轴.此外,该书提到了与"中位数"类别相关的Blum-Floyd-Pratt-Rivest-Tarjan(BFPRT).
大多数版本的快速排序都会选择（例如）三个元素（通常是第一个、中间和最后一个）的中位数，即通常所说的中位数 3 的快速排序。仅从中间元素开始，因为枢轴通常不符合除快速排序之外的任何名称。
编辑（很久以后，在看到问题中的编辑之后）：看来您正在谈论的是使用“中位数的中位数”算法来选择快速排序的枢轴元素。中位数的中位数算法因独立用作霍尔选择算法的替代（或改进，取决于您的观点）而闻名。众所周知，这可以在线性时间内找到中位数（或其他排名，但在这种情况下我们只关心中位数）。
底线是排序实际上仍然是快速排序。霍尔对选择枢轴元素的描述既不需要也不禁止中位数选择媒体：
分区过程的第一步是选择一个特定的键值，该键值已知在要排序的段中的项目的键的范围内。确保这一点的一个简单方法是选择段中一项的实际键值。所选的键值将称为绑定。
当然，现在几乎每个人都称其为“枢轴”而不是“界限”，但这大多是无关紧要的。用于选择枢轴/边界的方法尚未确定。