然而本题，排序的方法还不是复杂度最好的，有一种叫做 Nth−Element 的方法，可以在 O(n) 的时间求得数组中第 K 大的数。 这个方法的思路借鉴了快排的思想，每次选出1个数 Vi ，用来把整个数组的数分成 2 部分，大于 Vi 的与小于等于 Vi 的，那么每次可以排除掉将近一半的数。所以 Log(n) 次后，可以找到最终要找的数。按照上面复杂度分析所讲的。 n+n/2+n/4+....1<2n 所以复杂度为 O(n) 。