MATLAB求最大的k个元素

在matlab的内置函数中已经给出了sort和min,max的实现,都是比较高效的。但是我们常常遇到这种情况,就是要在一个矩阵或者是向量中取出最大的前k个元素,k一般相比元素的总数量要小很多。 这个时候,一般最朴素的做法是先用sort排序,然后取前n个,这样得到的时间复杂度为O(n*log(n))。假设向量有n个元素。 或者当k远远小于n时,可以考虑重复调用max或min,这时的复杂度为O(k*n)。

Bruno Luong 给出了一个用部分快速排序实现的算法,复杂度为O(n+k*log(k)),比上面的解决方法更加优雅和有效。 这个算法的mex实现可以在MatlabCentral上免费下载

Min/Max Selection mex实现

常常有面试题要求O(n)时间内求第k大的元素,可以参考这个算法的思路。