>本文作者：梁开权，叩丁狼高级讲师。原创文章，转载请注明出处。 我们知道排序算法有很多： 1. 冒泡算法：通过两层for循环，外层第一次循环找到数组中最大的元素放置在倒数第一个位置，第二次循环找到第二大的元素放置在倒数第二个位置。。。循环N次就可以找到TopN。 缺点：冒泡排序内层循环需要大量交换元素。复杂度介于O(n)和O(n^2)之间。 2. 快速排序：选一个基准元素，每次排序可以将这个基准元素搁置在正确的位置，左边都是比基准小的元素，右边都是比基准大的元素从而将数组分成左右两部分，分而治之。TopN问题也同样如此，选择一个基准元素并通过快速排序将基准元素搁置在正确的位置，如果左边的元素个数小于1000，那么继续从基准右边排序，如果左边元素个数大于1000，那么从基准左边排序，直到基准的位置正好在1000，结束。 缺点：第一次排序复杂度是O(n),第二次排序复杂度是O(n/2),第三次排序复杂度是O(n/4).... 3. 文件存储，分而治之: 将比基准小的元素存储在txt1中，比基准大的文件存储在txt2中，然后通过类似方法二的形式，最后求出TopN。 缺点：磁盘读取，写入次数过多。 4. MapReduce:单机内存和性能确实受限，那么我们可以将10亿个分段存储在不同的机器上，每台机器计算各自的TopN，最后汇总。 缺点：空间换时间。 ## 最优解：小顶堆 在内存中维护一个长度为N的数组，根据堆的性质，每一个节点都比他的左右子节点小，先取出前N个数并构建小顶堆，然后将所有数据与堆顶比较大小，如果比堆顶小就直接丢弃，如果比堆顶大则替换堆顶，并且重新构建这个堆。 构建小顶堆的过程：先要找到最后一个非叶子节点，数组的长度为6，那么最后一个非叶子节点就是：长度/2-1，也就是6/2-1=2，然后下一步就是比较该节点值和它的左右节点值，如果该节点大于其左\右子树的值就交换（意思就是将最小的值放到该节点）。如果该节点不是叶子结点，则递归这一过程，直到这个节点变成叶子节点。 具体执行代码如下： ``` public class Top1000 { public static int N = 1000; //Top1000 public static int LEN = 100000000; //1亿个整数 public static int arrs[] = new int[LEN]; public static int result[] = new int[N]; //在内存维护一个长度为N的小顶堆 public static int len = result.length; //堆中元素的有效元素 heapSize<=len public static int heapSize = len; public static void main(String[] args) { Random random = new Random(); //生成随机数组 for (int i = 0; i < LEN; i++) { arrs[i] = random.nextInt(Integer.MAX_VALUE); } //构建初始堆 for (int i = 0; i < N; i++) { result[i] = arrs[i]; } //构建小顶堆 long start = System.currentTimeMillis(); buildMinHeap(); for (int i = N; i < LEN; i++) { if (arrs[i] > result[0]) { result[0] = arrs[i]; minHeap(0); } } System.out.println(LEN + "个数，求Top" + N + "，耗时" + (System.currentTimeMillis() - start) + "毫秒"); print(); } /** * 自底向上构建小堆 */ public static void buildMinHeap() { int size = len / 2 - 1; //最后一个非叶子节点 for (int i = size; i >= 0; i--) { minHeap(i); } } /** * i节点为根及子树是一个小堆 * * @param i */ public static void minHeap(int i) { int l = left(i); int r = right(i); int index = i; if (l < heapSize && result[l] < result[index]) { index = l; } if (r < heapSize && result[r] < result[index]) { index = r; } if (index != i) { int t = result[index]; result[index] = result[i]; result[i] = t; //递归向下构建堆 minHeap(index); } } /** * 返回i节点的左孩子 * * @param i * @return */ public static int left(int i) { return 2 * i; } /** * 返回i节点的右孩子 * * @param i * @return */ public static int right(int i) { return 2 * i + 1; } /** * 打印 */ public static void print() { for (int a : result) { System.out.print(a + ","); } System.out.println(); } } ```