选择算法

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

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

通过排序选择

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

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

参见

• 序优化

外部链接

• "Lecture notes for January 25, 1996: Selection and order statistics （页面存档备份，存于互联网档案馆）", ICS 161: Design and Analysis of Algorithms, David Eppstein