在线性级别时间内找出无序序列中的第k个元素

在一个无序序列中找出第k个元素，对于k很小或者很大时可以采取特殊的方法，比如用堆排序来实现 。但是对于与序列长度N成正比的k来说，就不是一件容易的事了，可能最容易想到的就是先将无序序列排序再遍历即可找出第k个元素。由于任何基于比较的排序算法不可能用少于Θ(N lgN)次比较来实现将所有元素排序，所以采用排序的方法的时间复杂度是线性对数级别的。在一个无序序列中找出第k个元素，对于k很小或者很大时可以采取特殊的方法，比如用堆排序来实现 。