在 1 亿个整数 中找到 最大的前 100 个数，可以使用以下高效方法：
1. 小顶堆（优先队列，推荐）
思路
使用 小顶堆（Min Heap） 维护前 100 个最大的数：
优先队列（PriorityQueue） 维护 100 个元素，堆顶是最小的元素。
遍历 1 亿个数，如果当前数比堆顶大，则替换并调整堆。
时间复杂度
插入堆的时间复杂度：
O(log 100) ≈ O(7)处理 1 亿个数的时间复杂度：
O(10^8 * log 100) ≈ O(10^8)
代码示例
import java.util.PriorityQueue;
import java.util.Random;
public class Top100MaxNumbers {
public static void main(String[] args) {
int n = 100000000; // 1亿个整数
int topK = 100; // 需要找的前100个最大值
Random random = new Random();
// 小顶堆（默认是最小堆）
PriorityQueue<Integer> minHeap = new PriorityQueue<>(topK);
for (int i = 0; i < n; i++) {
int num = random.nextInt(Integer.MAX_VALUE); // 生成随机数
if (minHeap.size() < topK) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
minHeap.poll(); // 移除最小值
minHeap.offer(num);
}
}
// 输出结果
System.out.println("Top 100 max numbers:");
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll());
}
}
}2. 快速选择算法（QuickSelect，适用于小数据）
思路
类似快速排序，但只递归到第
n-100个元素，不需要完整排序。时间复杂度：
O(N)，最坏情况O(N^2)
代码
import java.util.Random;
public class QuickSelectTop100 {
public static void main(String[] args) {
int n = 100000000;
int topK = 100;
int[] arr = new Random().ints(n, 0, Integer.MAX_VALUE).toArray();
int index = partition(arr, 0, arr.length - 1, arr.length - topK);
int[] top100 = new int[topK];
System.arraycopy(arr, index, top100, 0, topK);
System.out.println("Top 100 max numbers:");
for (int num : top100) {
System.out.println(num);
}
}
private static int partition(int[] arr, int left, int right, int k) {
if (left == right) return left;
int pivotIndex = left + new Random().nextInt(right - left + 1);
int pivot = arr[pivotIndex];
int storeIndex = left;
swap(arr, pivotIndex, right);
for (int i = left; i < right; i++) {
if (arr[i] < pivot) swap(arr, storeIndex++, i);
}
swap(arr, storeIndex, right);
if (storeIndex == k) return storeIndex;
else if (storeIndex < k) return partition(arr, storeIndex + 1, right, k);
else return partition(arr, left, storeIndex - 1, k);
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}3. 外部排序（适用于数据太大，内存不足的情况）
如果 数据无法全部放入内存，可以使用 外部排序：
分块读取（Chunking）：将 1 亿个数分为多个小文件，每个文件 使用小顶堆选出 100 个最大数。
归并排序（Merge Sort）：合并多个小文件中的最大数，最终选出 100 个最大数。
思路
设每个块 包含 100 万个数，分成
100个块，每个块独立选出 100 个最大值（O(n log 100)）。最终合并
100个块中的 100 * 100 = 10000 个数，再用小顶堆选出最终 100 个最大值。
代码示例
import java.io.*;
import java.util.PriorityQueue;
import java.util.Scanner;
public class ExternalSortTop100 {
private static final int CHUNK_SIZE = 1000000; // 100万一块
public static void main(String[] args) throws IOException {
String inputFile = "bigdata.txt"; // 假设存储1亿个整数
String[] chunkFiles = splitIntoChunks(inputFile);
// 小顶堆合并各个chunk的前100
PriorityQueue<Integer> minHeap = new PriorityQueue<>(100);
for (String chunkFile : chunkFiles) {
try (Scanner scanner = new Scanner(new File(chunkFile))) {
while (scanner.hasNextInt()) {
int num = scanner.nextInt();
if (minHeap.size() < 100) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
minHeap.poll();
minHeap.offer(num);
}
}
}
}
System.out.println("Top 100 max numbers:");
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll());
}
}
private static String[] splitIntoChunks(String inputFile) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader(inputFile));
int chunkIndex = 0;
String line;
while ((line = reader.readLine()) != null) {
// 分块写入文件
int[] numbers = new int[CHUNK_SIZE];
int i = 0;
do {
numbers[i++] = Integer.parseInt(line);
} while (i < CHUNK_SIZE && (line = reader.readLine()) != null);
// 选出当前块的前100个最大值
PriorityQueue<Integer> minHeap = new PriorityQueue<>(100);
for (int num : numbers) {
if (minHeap.size() < 100) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
minHeap.poll();
minHeap.offer(num);
}
}
// 写入临时文件
try (BufferedWriter writer = new BufferedWriter(new FileWriter("chunk_" + chunkIndex + ".txt"))) {
while (!minHeap.isEmpty()) {
writer.write(minHeap.poll() + "\n");
}
}
chunkIndex++;
}
return new File(".").list((dir, name) -> name.startsWith("chunk_"));
}
}总结
推荐方案：
内存足够 → 小顶堆
数据较小（百万级） → 快速选择
数据太大（超过内存） → 外部排序
对于 1 亿个整数，小顶堆（优先队列）是最优选择，可以高效求出前 100 个最大数。
