快排思想找1亿个数的前100个最大值

绝地灬酷狼 2023-06-07 10:58 20阅读 0赞

从一亿个随机数里寻找前100个最大的数，如果根据常规的快速排序排完一亿个数，再取前100个数，那么耗时11~12s（VM内存设置 ：-Xms256m -Xmx1024m），因为只需要取前100个最大值，所以不必全都排序，只需根据快速排序的思想，判断pivot的当前位置 i 与99(第100个数组下标)的关系：

quickSortTop(int\[\] arr, int start, int end)  
如果i等于99，那么数组前100个元素肯定是最大的（排在pivot左边的数都比右边的大）,退出递归，  
如果i小于99，那么在(i,end\]里查找前100-(i+1)最大值，即继续递归，  
如果i大于99，那么在\[0,i-1\]里查找前100个，即继续递归。

变形到的快排查找到，耗时在400~900ms，相比之下耗时减少了一个数量级，下面是测试代码：

package com;
    
    import java.util.Random;
    
    public class TestQuickSortWithin100 {
    
    	// 一亿个数
    	private static final int NUMBER = 10000 * 10000;
    	// 前100个数
    	private static final int TOPNUMBER = 100;
    
    	public static void main(String[] args) {
    		int[] arr = new int[NUMBER];
    
    		// 随机生成一亿个数
    		Random random = new Random();
    		for (int i = 0; i < NUMBER; i++) {
    			arr[i] = random.nextInt();
    		}
    
    		// 计时
    		long begin = System.currentTimeMillis();
    
    		TestQuickSortWithin100.quickSortTop(arr, 0, NUMBER - 1);
    
    		long end = System.currentTimeMillis();
    		long total = (end - begin);
    
    		System.out.println("找到前" + TOPNUMBER + "个最大值(用时：" + total + "ms)：");
    
    		// 输出的判断是否满足要求,这里只输出前1000个数
    		int key = arr[TOPNUMBER - 1];
    		for (int j = 0; j < TOPNUMBER * 10; j++) {
    			if (j >= TOPNUMBER && key < arr[j]) {
    				System.out.print("\n查找失败");
    			}
    			if (j == TOPNUMBER) {
    				System.out.println("\n下面的数都小于所有前" + TOPNUMBER + "个数：");
    			}
    			System.out.print(arr[j] + " , ");
    			if ((j + 1) % 5 == 0)
    				System.out.println();
    		}
    	}
    
    	public static void quickSortTop(int[] arr, int start, int end) {
    		if (start > end)
    			return;
    
    		int pivot = arr[start];
    		int i = start;
    		int j = end;
    		while (i < j) {
    			while (i < j && arr[j] <= pivot) {
    				j--;
    			}
    			while (i < j && arr[i] >= pivot) {
    				i++;
    			}
    			if (i < j) {
    				arr[i] += arr[j];
    				arr[j] = arr[i] - arr[j];
    				arr[i] -= arr[j];
    			}
    		}
    		arr[start] = arr[i];
    		arr[i] = pivot;
    
    		// 常规的快速排序写法
    		// quickSortTop(arr, start, i - 1);
    		// quickSortTop(arr, i + 1, end);
    
    		// 查找前TOPNUMBER最大值的数
    		// 判断pivot的位置i是否等于TOPNUMBER-1:
    		// 如果i等于TOPNUMBER-1，那么数组前TOPNUMBER个是最大的,退出
    		// 如果i小于TOPNUMBER-1，那么在(i,NUMBER]里查找前TOPNUMBER-(i+1)最大值（继续递归）
    		// 如果i大于TOPNUMBER-1，那么在[0,i-1]里查找前TOPNUMBER个（继续递归）
    		if (i == TOPNUMBER - 1) {
    			return;
    		} else if (i < TOPNUMBER - 1) {
    			quickSortTop(arr, i + 1, end);
    		} else {
    			quickSortTop(arr, 0, i - 1);
    		}
    
    	}
    }