给定一个包含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 ...