选择算法 在计算机科学中选择算法是一种在列表或数组中找到第k个最小数字的算法这样的数字被称为第k个顺序统计量该算法寻找的对象主要有三种最小最大和中位数已知存在On最坏情况下为线性时间的选择算法还有对于结构化数据可能有次线性的表现的算法在极端的情况下对于已排序数据是O选择是一些更复杂问题的子问题如最近邻和最短路径问题 许多选择算法是由排序算法推广而来反之一些排序算法可由反复应用选择算法推导出来 最简单的选择算法是通过遍历列表找到最小或最大的元素在此过程中跟踪当前的最小或最大值这种算法与选择排序有关相反地最困难的选择算法是寻找中位数这必然需要n的空间 事实上一个专门的中位选择算法可用来构造一个一般选择算法例如中位数的中位数英语Median of medians已知最好的选择算法是快速选择quickselect它与快速排序有关和快速排序类似它有渐进最佳的复杂度但是最坏情况的复杂度较差不过这可以通过调整基准pivot的选择来优化