快速选择 在计算机科学中快速选择英語Quickselect是一种从无序列表找到第k小元素的选择算法它从原理上来说与快速排序有关与快速排序一样都由托尼霍尔提出的因而也被称为霍尔选择算法 同样地它在实际应用是一种高效的算法具有很好的平均时间复杂度然而最坏时间复杂度则不理想快速选择及其变种是实际应用中最常使用的高效选择算法 快速选择的总体思路与快速排序一致选择一个元素作为基准来对元素进行分区将小于和大于基准的元素分在基准左边和右边的两个区域不同的是快速选择并不递归访问双边而是只递归进入一边的元素中继续寻找这降低了平均时间复杂度从On log n至On不过最坏情况仍然是On 与快速排序一样快速选择一般是以原地算法的方式实现除了选出第k小的元素数据也得到了部分地排序