给定一个包含n个元素的数组，怎样从中找出第k大的数。
What is the most efficient algorithm to find the kth smallest element in an array having n elements?
此问题被称为求第k顺序统计量（kth order statistic）。
求解该问题的线性时间算法（既包括确定性算法，也包括非确定性算法）列举如下：
1. Quickselect （快速选择）
2. Median-of-medians (BFPRT) （中位数的中位数）
3. Introselect （内省选择）
4. Unnamed algorithm using soft heaps （使用软堆的未命名算法）
快速选择 （Quickselect）
快速选择算法可以在期望时间O(n)求解此问题。快速选择算法是快速排序算法的变种。
Quickselect is a randomized algorithm that solves the problem in O(n) expected time. Quickselect is an adaptation of the quicksort algorithm.
更多信息可参阅：http://en.wikipedia.org/wiki/Quickselect
中位数的中位数 （Median-of-medians (BFPRT) ）
中位数的中位数算法可以在确定性时间Theta(n)求解此问题。但是，该算法复杂度的常系数很高。
The median-of-medians algorithm solves the problem deterministically in Theta(n) time. The constant value for the median-of-medians algorithm is pretty high, however.
更多信息可参阅: http://en.wikipedia.org/wiki/Median_of_medians
内省选择 （Introselect）
内省选择算法首先调用快速选择算法，但如果其运算次数超过O(n)时，缺省使用中位数的中位数算法，确保最坏运行时间为Theta(n)。
The introselect algorithm starts off by using quickselect, but as soon as it deviates from O(n) operations, it defaults to using the median-of-medians algorithm, ensuring a worst-case run-time of Theta(n).
更多信息可参阅：http://en.wikipedia.org/wiki/Introselect
使用软堆的未命名算法 （Unnamed algorithm using soft heaps）
该选择算法为确定性算法，通过向一个软堆中插入和删除元素实现，时间复杂度为Theta(n)。
This selection algorithm involves inserting and deleting elements from a soft heap and runs deterministically in \Theta(n) time.
更多信息可参阅：http://en.wikipedia.org/wiki/Soft_heap#Applications
原文链接：http://www.quora.com/What-is-the-most-efficient-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements
本文链接：http://bookshadow.com/weblog/2015/02/04/linear-time-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
