概述
一种做法是我们直接进行一个堆排序，或者快排，然后打印前100个即可，但是这样子比较耗时间；
平均下来快排都在9000多ms，而堆排就更大，32s多；所以我们不能简单粗暴的直接快排或者堆排，要对其进行相对的优化；（这种做法不可取，要优化！！！）
下面我们看具体方法：
方法一：基于quicksort实现的原理如下
（ps:前提是快排是要懂得，不懂得可以请各位移步去看我这一篇博文：快速排序）
1. 假设数组为 array[N] (N = 1 亿)，首先利用一次quicksort的原理把array分成两个部分，左边部分比基准值大， 右边部分比基准小。 得到基准值在整个数组中的位置，假设是 k.
2. 如果 k 比 99 大，原数组变成了 array [0, ... k - 1]， 然后在数组里找前 100 最大值。 （继续递归）
3. 如果 k 比 99 小， 原数组变成了 array [k + 1, ..., N ]， 然后在数组里找前 100 - (k + 1) 最大值。（继续递归）
4. 如果 k == 99, 那么数组的前 100 个值一定是最大的。（退出）
代码部分：
//找出一亿数据里面的前100个 快排思路
//先进行一次快排 找到基准值排序后的位置 start，使得左边数全部大于它，右边数全部小于它
//然后对比 start与99的大小 因为数组从0开始的所以对比99
// start>99的话，就从arr[0,start-1] 中找前100个最大的、
// start<99的话，就从arr[start+1,end] 中找前100-(start+1)个最大的
// start==99的话，那么数组的前 100 个值一定是最大的 (不用排序直接返回 因为只是要前100最大的，没有要求说对这100个数再进行排序)
public class FastTake100 {
public static void quickSort(int[] arr, int left, int right, int k) {
//1.一次快排找出基准值最后的位置:start
if (left >= right) {
return;
}
int start = left;
int end = right;
int num = arr[left];//以最左边为基准值
while (start < end) {
while (start < end && num >= arr[end]) {
end--;
}
while (start < end && num <= arr[start]) {
start++;
}
if (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
arr[left] = arr[start];
arr[start] = num;
//2.进行判断 然后继续递归
if (start < k - 1) {
//start<99的话，就从arr[start+1,right] 中找前100-(start+1)个最大的
quickSort(arr, start + 1, right, k - start - 1);
} else if (start > k - 1) {
//start>99的话，就从arr[0,start-1] 中找前100个最大的
quickSort(arr, 0, start - 1, k);
} else {
//start==99的话，那么数组的前 100 个值一定是最大的 直接返回即可
return;
}
}
public static void main(String[] args) {
int[] arr = new int[100000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 100000000);
}
int k = 100;
//开始时间
long one = System.currentTimeMillis();
quickSort(arr, 0, arr.length - 1, k);
//结束时间
long two = System.currentTimeMillis();
//打印耗时
System.out.println(two - one);
//打印top100
for (int i = 0; i < 100; i++) {
System.out.println(arr[i]);
}
}
}
总结： 基于quicksort原理的方法运行时间不稳定（每次运行时间相差大）；不管是固定中枢轴，还是中枢轴采用三数取中法，每次运行时间差距都挺大，30ms-1000ms不等。
方法二：minHeap（小顶堆实现）
最大堆 max-heap（大顶堆）：每个节点的键值（key）都大于或等于其子节点键值
最小堆 min-heap（小顶堆）：每个节点的键值（key）都小于或等于其子节点键值
# 当前节点 i：
1.则其父节点： i/2 （因为/默认就是向下取整）或者(i-1) /2；
2.两个孩子节点：2i+1; 2i+2;
有些小伙伴可能想到，既然是找top100，为什么不是用大顶堆来实现，而是用小顶堆呢？
在写之前，我也有这样的想法，带着疑惑我们来看下面的分析：
（ps:前提是堆排序是要懂得，不懂得可以请各位移步去看我这一篇博文：堆排序实现）
知道堆排序的具体步骤以及相应的代码已经看懂，会自己写出来后，我们来看看本题的分析：
- 先new一个100大小的数组 value[100]；
- 然后我们直接把原始数组arr的前100个数初始化给value；（看清楚哦，前100个数是指：是0-99的下标的值，这里不对arr进行堆排序）；
- 把value数组，进行小顶堆化，这样堆顶的元素value[0]就是最小的；
- 核心：我们 设 i 从k开始，到arr的长度结束；每次比较value[0]与arr[i]的的大小，只要arr[i] > value[0] ，我们就把arr[i] 赋值给value[0]，此时堆顶元素就是一个比较大的元素，然后我们重新进行一次heapify（小顶堆化），再把堆顶置于最小，继续与arr[i]比较，重复上述过程直到遍历完整个arr数组；（每次都会把最小的元素替换掉）
- 遍历完以后，我们的value数组里存的就是 top100大的数字了；
- 打印value数组，就可以看到结果；
下面看代码：
import java.util.Random;
找出一亿数据里面的前100个 堆排思路 利用minHeap 小顶堆
public class HeapTake100 {
public static int[] heapSort(int[] arr) {
//new 一个数组存储top100的元素
int[] value=new int[100];
//初始化value数组
for (int i = 0; i < 100; i++) {
value[i]=arr[i];
}
//把value数组构建成小顶堆
buildHeap(value);
for (int i = 100; i <arr.length ; i++) {
//若满足条件就赋值
if (value[0]<arr[i]){
value[0]=arr[i];
//重新小顶堆化
heapify(value,0,value.length);
}
}
return value;
}
//从第一个非叶子节点开始 往上遍历建立堆
public static void buildHeap(int[] arr) {
//数组的长度/2 - 1 就是：第一个非零节点的位置
int n=arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, i, n);
}
}
//heapify 真正用来调整堆的方法
public static void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int max = i;
if (left < len && arr[left] < arr[max]) {
max = left;
}
if (right < len && arr[right] < arr[max]) {
max = right;
}
if (max != i) {
swap(arr, max, i);
heapify(arr, max, len);
}
}
//堆排序用来交换的方法
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//执行的主函数
public static void main(String[] args) {
int[] arr = new int[100000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 100000000);
}
//计算消耗时间
long t1=System.currentTimeMillis();
int[] value=heapSort(arr);
long t2=System.currentTimeMillis();
System.out.println(t2-t1);
//打印结果数组
for (int i : value) {
System.out.println(i);
}
}
}
问题
那么又有人问了：为什么不用大顶堆？
假如使用大顶堆，当value[0] < arr[i] 时候，我们替换，会发现value[0] 始终是整个堆里最大的，这样子操作，只是每次把value[0] 换了一个最大的，也就是最后只找到 top1大的元素；
-------当然实践出真知，各位可以自己去动手尝试一下写，然后看看要是改成大顶堆，每次用大顶堆最后一个元素进行比较交换，看看会会出现什么样的结果。
总结：
基于最小堆方法运行时间很稳定（每次运行时间相差很小 基本都是52ms左右）；
