我在读这本书的算法果壳中的的由O'Reilly Media出版，我正在读一节排序算法，发现一个叫中位数排序。因为我从来没有听说过，并从CS3我的书（其中包括算法）没有它上市，我GOOGLE了它，并试图寻找它在维基百科上，并没有发现什么。我将非常AP preciate，如果有人可以提供名字，我可以很容易地查找算法下设或点我一下其他资源。谢谢你。

I'm reading the book Algorithms in a Nutshell published by O'Reilly Media and I was reading the section on sorting algorithms and found one called Median Sort. Since I had never heard of it before and my textbook from CS3 (which covered algorithms) did not have it listed, I googled it and tried looking it up on Wikipedia and found nothing. I would greatly appreciate it if someone could provide the name I could easily look the algorithm up under or point me to other resources about it. Thank you.

另外，从我可以告诉的算法，它本质上是快速排序，除了它总是使用中值作为支点。通过中间值我的意思是它似乎扫描项目的数组，并选择中间值作为支点，不挑数组作为支点的中间项。此外，书中提到了百隆 - 弗洛伊德 - 普拉特 - 维斯特-的Tarjan（BFPRT）相对于中位数之类的。

Also, from what I can tell about the algorithm, it's essentially Quicksort except it always uses the median value as the pivot. By median value I mean it seems to scan the array of items and pick the middle value as the pivot, not pick the middle item in the array as the pivot. Also, the book mentions a Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) in relation to the "Median" sort.

推荐答案

大多数版本的快速排序选秀权（例如）三要素中位数（通常是第一个，中间和最后），给予什么通常称为3快速排序中位数。刚开始使用的中间元素作为支点通常并不符合不仅仅是快速排序其他任何名称。

Most versions of quicksort pick (for example) the median of three elements (typically the first, middle and last), giving what's normally called a median of 3 Quicksort. Just starting with the middle element as the pivot doesn't usually qualify for any name other than just Quicksort.

编辑（多的后面，看到编辑在提问之后）：看来，你所谈论的是使用算法的中位数中位数选择了快速排序的支点元素。的中位数算法中位数是更好地了解被单独使用作为替代（或细化，这取决于你的观点），霍尔的选择算法。这是已知的寻找中值（或其它级别，但在这种情况下，我们只关心中位数）线性时间

Edit (much later, after seeing the edit in the question): it appears that what you're talking about is using the "median of medians" algorithm to choose the pivot element for a QuickSort. The median of medians algorithm is better known for being used independently as an alternative to (or refinement of, depending on your viewpoint) Hoare's Select algorithm. This is known to find the median (or other rank, but in this case we only care about median) in linear time.

底线是，排序的是真的还是一个快速排序。选择支点元素的霍尔的描述既不要求也不禁止位数选择一个媒体：

The bottom line is that the sort is really still a Quicksort. Hoare's description of choosing the pivot element neither requires nor prohibits a media of medians selection:

分区方法的第一个步骤是选择这是众所周知的是在这是要排序的段的项目的键的范围内的特定键的值。确保这方面的一个简单的方法就是选择的段中的一个项目的实际键值。所选择的键值将被称为的的约束的。

The first step of the partition process is to choose a particular key value which is known to be within the range of the keys of the items in the segment which is to be sorted. A simple method of ensuring this is to choose the actual key value of one of the items in the segment. The chosen key value will be called the bound.

当然，几乎每个人都现在称之为支点，而不是绑定，但是这主要是无关紧要的。用于选择支点的方法/势必是开放的。

Of course, nearly everybody now calls it the "pivot" instead of the "bound", but this is mostly irrelevant. The method used to choose the pivot/bound is left open.