选择算法

计算机科学中,选择算法是一种在列表数组中找到第k个最小数字的算法;这样的数字被称为第k个顺序统计量。该算法寻找的对象主要有三种:最小最大中位数。已知存在O(n)(最坏情况下为线性时间)的选择算法,还有对于结构化数据可能有次线性的表现的算法;在极端的情况下,对于已排序数据是O(1)。选择是一些更复杂问题的子问题,如最近邻最短路径问题。 许多选择算法是由排序算法推广而来,反之,一些排序算法可由反复应用选择算法推导出来。

最简单的选择算法是通过遍历列表找到最小(或最大)的元素,在此过程中跟踪当前的最小(或最大)值。这种算法与选择排序有关。相反地,最困难的选择算法是寻找中位数,这必然需要n/2的空间。 事实上,一个专门的中位选择算法可用来构造一个一般选择算法,例如中位数的中位数英语Median of medians。已知最好的选择算法是快速选择(quickselect),它与快速排序有关。和快速排序类似,它有渐进最佳的复杂度,但是最坏情况的复杂度较差。不过这可以通过调整基准(pivot)的选择来优化。

通过排序选择

通过对列表或数组的排序,然后选择所需的元素,选择算法可以规约排序算法。这种方法对于选择单个元素是低效的,但需要从数组中做出很多选择时是高效的。在这种情况下,仅仅需要一个起初一个代价昂贵的排序,紧接着就是各种便宜的选择操作了 – 对于数组而言是 O(1)。尽管对于链表而言,即使排序后,选择操作也需要 O(n),这是由于缺乏随机访问造成的。通常的,排序需要耗费 O(n log n) 的时间,其中 n 是列表的长度,尽管对于非比较算法而言可能更低一些,如基数排序计数排序

相比将整个列表或数组进行排序,还可以用偏排序来选择第 k 小或第 k 大的元素。第 k 小的(第 k 大的) 也就是偏排序后列表中最大的 (最小的) 那个 – 这在数组中会耗费 O(1) 来访问,在链表中会耗费 O(k)。

基于分区的选择

通过选择增量排序

参见

参考文献

外部链接