快速选择是一种算法,用于在无序集合中寻找指定秩的元素,例如最小元素、中位数或第十大元素,而无须对整个集合进行排序。它通过反复围绕选定的枢轴对元素进行分区,并仅在包含目标秩的分区内继续处理,从而解决选择问题。如果均匀随机地选择枢轴,并妥善处理相等的值,其期望运行时间与元素数量成线性关系,但最坏情况下的运行时间为平方级。快速选择与快速排序密切相关,不过它在每次分区后只处理其中一侧,而不是对两侧都进行排序。
选择与次序统计量
在排序后占据给定位置的元素称为次序统计量。采用从零开始的索引时,选择问题的输入是包含 个元素的集合和索引 ,其中 ,输出则是该集合排序后位于位置 的值。
例如,给定:
[9, 1, 8, 2, 7, 3, 6, 4, 5]
从零开始计数,秩为 的元素是 ,即中位数。找出这个值,无须确定其余元素的完整排序顺序。
秩按元素的出现次数计数,而不只计算互不相同的值。在已排序的集合 [2, 2, 5, 8] 中,秩为 和 的位置都包含 。具体实现可以返回选中的值、具有该值的对象,或标识其位置的迭代器或索引。
与排序算法不同,快速选择通常会让集合中的大部分元素仍处于无序状态。不过,原地实现可以保证:选定位置之前的元素均不大于选定值,之后的元素均不小于选定值。
分区原理
快速选择维护一个包含目标元素的当前处理区间。每次迭代执行三个操作:
- 从当前区间中选择一个枢轴。
- 根据元素与枢轴的比较结果对区间进行分区。
- 返回结果,或在包含目标秩的部分中继续处理。
三路分区将区间划分为三部分:小于枢轴的元素、与枢轴等价的元素,以及大于枢轴的元素。如果目标位置落在相等区域内,选择过程便已完成。否则,只需继续处理对应的外侧区域。
这种方式类似于分治法,但由于只继续求解一个子问题,快速选择也被称为剪枝搜索算法或减治算法。
伪代码
以下伪代码使用两端均包含在内的区间边界,目标索引则是从零开始的绝对索引:
quickselect(A, k):
要求 0 <= k < length(A)
left = 0
right = length(A) - 1
while left < right:
p = 从 left 到 right 之间均匀随机选取的整数
pivot = A[p] 的值
(lt, gt) = partition_three_way(A, left, right, pivot)
# A[left .. lt-1] 包含小于 pivot 的值
# A[lt .. gt] 包含与 pivot 等价的值
# A[gt+1 .. right] 包含大于 pivot 的值
if k < lt:
right = lt - 1
else if k > gt:
left = gt + 1
else:
return A[k]
return A[left]
这里,partition_three_way 原地重排当前区间,并返回相等区域的边界。在分区过程中,即使枢轴原先所在的数组位置被覆盖,也必须保证枢轴值仍然可用。
算法的正确性来自分区之间的次序关系:在排序顺序中,小于区域内的每个元素都位于相等区域内所有元素之前,大于区域内的每个元素则都位于其后。因此,目标秩不可能位于被舍弃的区域中。
分区约定
不同的分区过程并不遵循相同的约定。有些会将某个枢轴元素放到它排序后的最终位置;另一些则只返回分隔两个区域的边界,并不保证任何特定元素已处于其最终秩对应的位置。快速选择的实现必须采用与其分区过程相适应的更新规则。
存在重复值时,三路分区尤其有用。如果两路分区总是将所有相等值放到同一侧,那么在所有元素都相等的输入上,算法每次可能几乎无法缩小问题规模。三路分区则只需一次线性扫描就能处理完这种输入。
复杂度
普通快速选择的主要时间复杂度界限如下:
| 情况 | 运行时间 |
|---|---|
| 最佳情况 | |
| 均匀随机选择枢轴时的期望值 | |
| 最坏情况 |
这些界限假设比较和元素移动均耗费常数时间,且分区过程在线性时间内扫描当前区间。
期望线性时间
如果每个枢轴都能较为均衡地划分当前区间,各次分区的工作量便构成一个几何级数。例如,每次都保留约一半元素时,有:
均匀随机选择枢轴并不能保证每一步的分区都均衡。不过,枢轴的秩落在中间一半范围内的概率约为二分之一。这样的枢轴能保证,无论接下来需要搜索哪一侧,留下的元素都至多约占四分之三。实现一次这样的规模缩减所需的期望分区次数有常数上界,因此总工作量的期望为线性。
这里的期望是针对算法随机选择枢轴的过程而言的,并不要求输入顺序随机。因此,随机化快速选择是一种随机化算法:它总能返回正确结果,但运行时间不固定,通常归类为拉斯维加斯算法。
平方级的最坏情况
如果每次选出的枢轴都是极端元素,而目标秩始终位于较大的分区中,那么连续各次处理区间的大小可能为 。此时工作量为:
采用固定规则(例如始终选择第一个元素)时,某些特定排列的输入就可能导致这种行为。随机化使连续遇到不利选择的概率很低,但并不能消除平方级的最坏情况。
空间使用
采用原地分区的迭代实现,其辅助空间复杂度为 。递归实现还会消耗调用栈空间:随机选择枢轴时,期望递归深度为 ,最坏情况下的深度则为 。
为各个分区创建新集合的实现,在内存分配和内存开销方面有所不同;常数辅助空间是原地实现的性质,并非所有实现方式都具备这一性质。
枢轴选择与相关算法
枢轴的选择会显著影响实际性能。
- 固定位置枢轴的选择成本低,但在具有特定结构的输入上可能表现不佳。
- 均匀随机枢轴能对任意固定输入提供线性的期望运行时间。
- 三数取中及其他小样本方法在实践中通常能改善分区的均衡程度,但仅靠这些方法无法保证最坏情况下的线性时间。
- 更大的样本或考虑目标秩的采样方法可以提高选择效率,但需要付出额外的采样开销。
中位数的中位数
中位数的中位数算法提供了一种确定性的枢轴选择策略,能够保证最坏情况下的选择时间为线性。在其标准形式中,先将元素分成每组五个,找出各组的中位数,再递归选出这些中位数的中位数。
由此得到的枢轴保证可以舍弃固定比例的元素。其运行时间满足如下形式的界限:
由此可得 。与简单的随机化快速选择相比,这种更强的保证通常需要在枢轴选择上付出更多工作。
内省选择
内省选择将类似快速选择的高效过程与进展不足时启用的后备策略结合起来。其确切保证取决于后备策略的触发条件和策略本身。如果后备算法具有线性运行时间,同时还能限制此前已完成的工作量,就可以保证最坏情况下的线性选择时间。仅仅设置递归深度限制,本身并不足以确立这一界限。
应用与局限
只需要排序结果中的一小部分时,快速选择很有用:
- **中位数与样本分位数:**选择算法无须对整个样本排序,就能取得相关秩对应的观测值。采用插值的分位数定义可能需要两个相邻的次序统计量。
- **提取前 个元素:**在适当的边界处分区,即可分离出最小或最大的 个元素。随后只对该子集排序,期望工作量为 。
- **几何数据结构:**构建平衡KD树时,可以通过选择中位数来划分点集。
- **数据处理:**基于秩的截断和修剪操作可以使用选择算法,而不必进行完整排序。
数组或其他可变的随机访问序列,是实现原地快速选择的自然选择。该方法会改变元素顺序,而且通常不稳定:关键字相等的记录未必保留原有的相对顺序。若要保留原始排列,可能需要复制数据或使用辅助索引数组。
比较操作必须定义一致的顺序。对于浮点非数值,需要明确规定排序策略,因为普通比较无法一致地确定它们与其他值之间的次序。
快速选择还假定能够反复访问当前处理的集合。对于流式数据或大到无法装入内存的集合,优先队列、近似分位数方法或外存选择算法可能更合适。如果为许多个秩分别独立执行快速选择,可能会重复进行分区工作;此时,共享分区工作的多重选择或完整排序可能更为合适。
历史
快速选择由 C. A. R. 霍尔于 1961 年提出,当时名为 Algorithm 65: Find(算法 65:查找)。它与快速排序一同发展,采用了相同的核心思想,即围绕枢轴进行分区。快速排序递归地对两个分区都进行排序,而快速选择只搜索相关的分区;正是这一差别,使快速排序的期望运行时间为 ,而快速选择的期望运行时间为 。