[java] public static int[] findTopNValues(int[] anyOldOrderValues, int n) { Arrays.sort(anyOldOrderValues); int[] result = new int[n]; System.arraycopy(anyOldOrderValues, anyOldOrderValues.length - n, result, 0, n); return result; } [/java] Arrays.sort(int[])使用的是快排，平均的时间复杂度是O( n lg(n))，在一般情况下已经足够好。那么有没有平均情况下O(n)复杂度的算法？这个还是有的，这道题目其实是选择算法的变形，选择一个数组中的第n 大元素，可以采用类似快排的方式划分数组，然后只要在一个子段做递归查找就可以，平均状况下可以做到O(n)的时间复杂度，对于这道题来说稍微变形下算法即可解决： [java] /**
[/java] 选择算法还有最坏情况下O(n)复杂度的实现，有兴趣可以读算法导论和维基百科。题外，我测试了下这两个实现，在我的机器上大概有2倍多的差距，还是很明显。
本文来源于"阿里中间件团队播客",原文发表时间" 2010-10-28"
相关资源：房屋结构注记与楼层注记合并