## 寻找数组第k大元素的线性时间选择算法 作者是 在线疯狂 发布于 2015年2月4日 在 算法.

What is the most efficient algorithm to find the kth smallest element in an array having n elements?

1. Quickselect （快速选择）

2. Median-of-medians (BFPRT) （中位数的中位数）

3. Introselect （内省选择）

4. Unnamed algorithm using soft heaps （使用软堆的未命名算法）

## 快速选择 （Quickselect）

Quickselect is a randomized algorithm that solves the problem in O(n) expected time.  Quickselect is an adaptation of the quicksort algorithm.

## 中位数的中位数 （Median-of-medians (BFPRT) ）

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.

## 内省选择 （Introselect）

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).

## 使用软堆的未命名算法 （Unnamed algorithm using soft heaps）

This selection algorithm involves inserting and deleting elements from a soft heap and runs deterministically in \Theta(n) time.

Pingbacks已关闭。