能否在O(n)时间内找出未排序数组中的k个最小元素？

没错，改进版Quickselect算法确实能在平均甚至最坏情况下达到O(n)的时间复杂度，用来找出未排序数组中的k个最小整数，完全匹配你的需求。

Quickselect的核心逻辑 #

• 选取一个基准元素（pivot），将数组划分为两部分：左侧是小于等于pivot的元素，右侧是大于pivot的元素
• 如果pivot的下标恰好为k-1（对应数组中第k小的元素，下标从0开始计数），那么左侧所有元素就是你要找的k个最小整数
• 如果pivot下标大于k-1，仅在左半分区重复上述操作；若下标小于k-1，则在右半分区继续查找

为什么能实现O(n)时间复杂度？ #

• 平均情况：每次分区会将数组大致分成均等的两部分，时间开销为 n + n/2 + n/4 + ... = 2n，属于O(n)级别
• 最坏情况优化：原始Quickselect最坏情况（比如每次选到极值当pivot）是O(n²)，但通过中位数的中位数（Median of Medians）方法选择pivot，能保证每次分区至少将数组拆分为1/5和4/5的两部分，从而把最坏时间复杂度稳定在O(n)

和堆方法的对比 #

用大小为k的最大堆实现的方法时间复杂度是O(n logk)，当k接近数组长度n时，logk趋近于logn，效率会明显低于Quickselect；而Quickselect无论k的取值大小，平均复杂度都是O(n)，最坏情况也能做到O(n)，更贴合你的需求。

实操注意点 #

• 不需要对整个数组排序：找到第k小的元素后，只需遍历一遍数组，收集所有小于等于该元素的项即可，这一步也是O(n)时间
• 重复元素处理：即使数组存在重复值，该逻辑依然有效，不会出现漏选或多选的问题

内容的提问来源于stack exchange，提问作者Daniel