题目描述
从10亿个随机整数中，找出前1000个最大数，要求以最小的时间复杂度及空间复杂度实现该需求。
解题思路
这道题的解决思路是将无序整数排列为有序序列，升序或降序，从中取出前1000个最大数。适用的排序算法包括：
- 插入排序、选择排序、冒泡排序、快速排序等，时间复杂度：
- 堆排序、归并排序，时间复杂度：
本题需要实现的是找出前1000个最大数，空间上可以只做1000条最大目标数组，其他数据与目标数组进行比较，如果比较值小于目标数组最小值，则抛弃。否则将最小值替换为比较值，并使用排序算法完成数据排序。本题采用算法为构建一个大小为1000的小顶堆排序（读者可自行查阅堆排序相关资料）。空间复杂度：
。排序算法及时间复杂度参考见下图：
| 排序方法 |
时间复杂度(平均) |
时间复杂度(最坏) |
时间复杂度(最好) |
空间复杂度 |
稳定性 |
复杂性 |
| 直接插入排序 |
O(n2) |
O(n2) |
O(n) |
O(1) |
稳定 |
简单 |
| 希尔排序 |
O(nlog2n) |
O(n2) |
O(n1.3) |
O(1) |
不稳定 |
较复杂 |
| 直接选择排序 |
O(n2) |
O(n2) |
O(n2) |
O(1) |
不稳定 |
简单 |
| 堆排序 |
O(nlog2n) |
O(nlog2n) |
O(nlog2n) |
O(1) |
不稳定 |
较复杂 |
| 冒泡排序 |
O(n2) |
O(n2) |
O(n) |
O(1) |
稳定 |
简单 |
| 快速排序 |
O(nlog2n) |
O(n2) |
O(nlog2n) |
O(nlog2n) |
不稳定 |
较复杂 |
| 归并排序 |
O(nlog2n) |
O(nlog2n) |
O(nlog2n) |
O(n) |
稳定 |
较复杂 |
| 基数排序 |
O(d(n+r)) |
O(d(n+r)) |
O(d(n+r)) |
O(n+r) |
稳定 |
较复杂 |
堆排序的特性
- 堆是一颗完整二叉树，除了最后一层节点不是满的，其余每一层从左到右都是满的。
- 堆中的每个节点的整数值，都小于或等于这个节点的子节点的整数。
- 对使用数组实现二叉树，满足以下条件公式：
-
- 节点的左子节点的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 < LEN; i++) {
if (arr[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);
}
}
}