快速选择
維基百科,自由的 encyclopedia
在计算机科学中,快速选择(英語:Quickselect)是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的,因而也被称为霍尔选择算法。[1] 同样地,它在实际应用是一种高效的算法,具有很好的平均时间复杂度,然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。
速览 快速选择, 概况 ...
快速选择 | |
---|---|
快速选择算法的动画演示:选择第22小的元素。(注意:这和条目中的算法不完全相同) | |
概况 | |
類別 | 选择算法 |
資料結構 | 数组 |
复杂度 | |
平均時間複雜度 | O(n) |
最坏时间复杂度 | О(n2) |
最优时间复杂度 | О(n) |
空間複雜度 | O(1) |
相关变量的定义 |
关闭
快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从O(n log n)至O(n),不过最坏情况仍然是O(n2)。
与快速排序一样,快速选择一般是以原地算法的方式实现,除了选出第k小的元素,数据也得到了部分地排序。