用快速选择+快速排序解决big_N/small_N问题

快速排序的一趟分区可以把数据按枢纽分成两部分，按需要执行多次分区操作就可以找到需要的N个数，然后对这N个数进行快速排序就可以得到需要的结果。

代码：

import java.util.*;
import java.util.stream.*;
import java.util.function.*;
import static java.lang.System.*;

public class BigSmall_N {
	public static void main(String[] args) {
		final int n=8;
		int i;
		boolean allRight=true;
		
		//生成一个Integer流，包含Count个大小位于[Min,Max]的随机数
		Stream<Integer> s=R.ints(Min,Max+1).limit(Count).mapToObj(num->new Integer(num));
		//将流转换成Integer数组
		Integer[] arr=s.toArray(Integer[]::new);
		//arr的升序拷贝
		Integer[] sortArrAsc=Arrays.copyOf(arr,arr.length);
		//arr的降序拷贝
		Integer[] sortArrDesc=Arrays.copyOf(arr,arr.length);
		Integer[] result;
		
		Arrays.sort(sortArrAsc);
		Arrays.sort(sortArrDesc,(a,b)->b.compareTo(a));
		
		out.printf("原数组的副本升序排序后：");
		printArray(sortArrAsc);
		out.print("原数组的副本降序排序后：");
		printArray(sortArrDesc);
		out.print("原数组：");
		printArray(arr);
		
		//计算并打印top1、small1，...，topN、smallN
		for(i=1;allRight && i<=n;i++) {
			out.printf("top_%d：",i);
			result=selectN(Arrays.asList(Arrays.copyOf(arr,arr.length)),i,true).toArray(new Integer[0]);
			printArray(result);
			allRight=Arrays.equals(result,Arrays.copyOfRange(sortArrDesc,0,i));
			//out.println(allRight);
			
			out.printf("small_%d：",i);
			result=selectN(Arrays.asList(Arrays.copyOf(arr,arr.length)),i,false).toArray(new Integer[0]);
			printArray(result);
			allRight=allRight && Arrays.equals(result,Arrays.copyOfRange(sortArrAsc,0,i));
			out.println(allRight ? "正确" : "错误");
		}
		
		out.printf("%s%n",(allRight ? "全部正确" : "有错误"));
	}
	
	static <T> void printArray(T[] arr) {
	//static <T extends Comparable<T>> void printArray(T[] arr) {
		Arrays.stream(arr).forEach(e->out.printf("%s,",e));
		out.println();
	}
	
	static <T extends Comparable<T>> void quickSort(List<T> l,int left,int right,boolean bigN) {
		if(l==null || l.size()==0 || left>=right) {
			return;
		}
		int start=left+1,end=right;
		T temp;
		while(start<=end) {
			if(bigN && l.get(start).compareTo(l.get(left))<=0 && l.get(end).compareTo(l.get(left))>0 ||
				!bigN && l.get(start).compareTo(l.get(left))>=0 && l.get(end).compareTo(l.get(left))<0
			) {
				temp=l.get(start);
				l.set(start,l.get(end));
				l.set(end,temp);
			}
			if(bigN && l.get(start).compareTo(l.get(left))>0 ||
				!bigN && l.get(start).compareTo(l.get(left))<0
			) {
				start++;
			}
			if(bigN && l.get(end).compareTo(l.get(left))<=0 ||
				!bigN && l.get(end).compareTo(l.get(left))>=0
			) {
				end--;
			}
		}
		start-=1;
		temp=l.get(left);
		l.set(left,l.get(start));
		l.set(start,temp);
		quickSort(l,left,start-1,bigN);
		quickSort(l,start+1,right,bigN);
	}
	
	static <T extends Comparable<T>> void quickSelect(List<T> l,int left,int right,int n,boolean bigN) {
		int i,pivot;
		T temp;
		
		if(l==null || l.size()==0 || n<=0 || left>=right) {
			return;
		}
		for(pivot=left,i=left+1;i<=right;i++) {
			if(bigN && l.get(i).compareTo(l.get(left))>0 ||
				!bigN && l.get(i).compareTo(l.get(left))<0
			) {
				++pivot;
				temp=l.get(pivot);
				l.set(pivot,l.get(i));
				l.set(i,temp);
			}
		}
		temp=l.get(left);
		l.set(left,l.get(pivot));
		l.set(pivot,temp);
		if(pivot+1<n) {
			//不足n在枢纽右边选
			quickSelect(l,pivot+1,right,n,bigN);
			//超过n在枢纽左边选
		} else if(pivot+1>n) {
			quickSelect(l,0,pivot-1,n,bigN);
		}
	}
	
	static <T extends Comparable<T>> List<T> selectN(List<T> l,int n,boolean bigN) {
		if(l==null || l.size()==0 || n<=0) {
			return Collections.emptyList();
		}
		n=n>l.size() ? l.size() : n;
		quickSelect(l,0,l.size()-1,n,bigN);
		l=l.subList(0,n);
		quickSort(l,0,n-1,bigN);
		return l;
	}
	
	static final int Min=1;
	static final int Max=99;
	static final int Count=21;
	static final Random R=new Random();
}

运行结果：