在计算机科学中，快速选择（）是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的，因而也被称为霍尔选择算法。 同样地，它在实际应用是一种高效的算法，具有很好的平均时间复杂度，然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。
快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度，从O(n log n)至O(n)，不过最坏情况仍然是O(n2)。
与快速排序一样，快速选择一般是以原地算法的方式实现，除了选出第k小的元素，数据也得到了部分地排序。
算法
快速排序中，有一个子过程称为分区，可以在线性时间里将一个列表分为两部分（left和right），分别是小于基准和大于等于基准的元素。下面是以list[pivotIndex]进行分区的伪代码：
function partition(list, left, right, pivotIndex)
pivotValue := list[pivotIndex]
swap list[pivotIndex] and list[right] // Move pivot to end
storeIndex := left
for i from left to right-1
if list[i] 2))：例如对一个升序排列的数组搜索其最大值，而每次都选择第一个元素作为基准值。
算法变体
最简单的快速排序变化是每次随机选择基准值，这样可以达到近乎线性的复杂度。更为确定的做法是采用“取三者中位数”的基准值选择策略，这样对已部分排序的数据依然能够达到线性复杂度。但是，特定人为设置的数组在此方法下仍然会导致最差时间复杂度，如大卫·穆塞尔所描述的“取三者中位数杀手”数列，这成为他发表算法的动机。
利用算法，可以在最坏情形下依然保证线性时间复杂度。但是这一方法中的基准值计算十分复杂，实际应用中并不常见。改进方法是在快速选择算法的基础上，使用“中位数的中位数”算法处理极端特例，这样可以保证平均状态与最差情形下的时间复杂度都是线性的，这也是算法的做法。
精确计算下，随机选择基准值策略最差会导致n(2+2\log 2+o(1)) \leq 3.4n + o(n)复杂度。采用可以使这一常数进一步减少，在最坏情形下达到 1.5 n + O(n^{1/2})。
参考文献
评论 (0)