题目描述

从10亿个随机整数中，找出前1000个最大数，要求以最小的时间复杂度及空间复杂度实现该需求。

解题思路

这道题的解决思路是将无序整数排列为有序序列，升序或降序，从中取出前1000个最大数。适用的排序算法包括：

• 插入排序、选择排序、冒泡排序、快速排序等，时间复杂度：

  

• 堆排序、归并排序，时间复杂度：

本题需要实现的是找出前1000个最大数，空间上可以只做1000条最大目标数组，其他数据与目标数组进行比较，如果比较值小于目标数组最小值，则抛弃。否则将最小值替换为比较值，并使用排序算法完成数据排序。本题采用算法为构建一个大小为1000的小顶堆排序（读者可自行查阅堆排序相关资料）。空间复杂度：

。排序算法及时间复杂度参考见下图：

堆排序的特性

1. 堆是一颗完整二叉树，除了最后一层节点不是满的，其余每一层从左到右都是满的。
2. 堆中的每个节点的整数值，都小于或等于这个节点的子节点的整数。
3. 对使用数组实现二叉树，满足以下条件公式：

• • 节点的左子节点的index为：2*index + 1
  • 节点的右子节点的index为：2*index + 2
  • 节点的父节点的index为：(index-1)/2

堆-完全二叉树

代码实现

说明：直接通过内存生成10亿条数据，容易产生堆内存溢出，可分批加载（如每次10000条）并完成小顶堆排序，并输出1000条数据。本例为方便测试验证，仅测试100条数据，查找最大的10条。

public class HeapSortTest {    //10亿数字.    public static int LEN = 100;    //TOP 1000    public static int TOP = 10 ;    //10亿数字数组    public static int arr[] = new int[LEN] ;    //TOP1000的小顶堆数组    public static int res[] = new int[TOP] ;    public static void main(String[] args) {        for (int i = 0; i < LEN; i++) {            arr[i] = new Random().nextInt(1000);        }        //构建初始堆        for (int i = 0; i < TOP; i++) {            res[i] = arr[i];        }        //构建小顶堆        long start = System.currentTimeMillis() ;        buildMinHeap(res);        for (int i = TOP; i  res[0]) {                res[0] = arr[i];                minHeap(res, 0);            }        }        System.out.println(LEN + "个数，求Top" + TOP + "，耗时" + (System.currentTimeMillis() - start) + "毫秒");        System.out.println(Arrays.toString(res));    }        /**         * 自底层向上构建一个小顶堆         */        public static int[] buildMinHeap(int[] arr) {        for(int i= arr.length/2 -1; i>=0; i--) {            minHeap(arr, i) ;        }        return arr ;    }    /**     * 根据插入的值,生成小顶堆     */    private static void minHeap(int[] arr, int current) {        int left = current*2 + 1, right = current*2 + 2, min = current ;        if(left < arr.length && arr[left] < arr[min]) {            min = left;        } else if(right < arr.length && arr[right] < arr[min]) {            min = right ;        }        if(min != current) {            int tmp = arr[min] ;            arr[min] = arr[current] ;            arr[current] = tmp ;            minHeap(arr, min);        }    }}