针对M个数中选择n个最大的数，其中M>>n,n>0，且M个数为乱序这一问题，给出如下思路
Example1.100个数中选择10个最大的数
思路一：对100个数进行排序（升序或降序均可），选择前10个（降序）或后10个（升序）即可。那么采用何种方法进行排序呢？
思路二：步骤1.将100个数放入一个数组中，叫做hunhrednumber在创建一个长度为10的空数组，叫做tennumber。
将hunhrednumber中的前十个数直接放入tennumber中即可，
从第11个数开始，依次与tennnumber中的10个数进行比较，若有比他小的，则替换带入，并把换出的数与余下的数继续进行比较，若发现有较小的数，继续换出以确定最终换出的数一定是原来数组中最小的数。若没有，则tennumber数组不变。
注意：在替换过程中替换出的数必须与余下的数继续进行比较替换，否则会出错。举个例子:
11个数中选出10个数
Int a[11]={23,34,45,56,67,12,25,24,68,78,30}
根据以上思路，Int b[10]={23,34,45,56,67,12,25,24,68,78}，第11 个数为30，若不继续比较替换，得到的数组为Int b[10]={30,34,45,56,67,12,25,24,68,78}，显然这个结果是错误的，因为换出的23明显比12大，12才是我们最终要换出的数字。
代码如下（java语言编写）
public class sort {
public static void main(String[] args) {
int hundrednumber[]=new int[100];
int tennumber[]=new int[10];
for(int i=0;i<=99;i++){
int rand=(int)(Math.random()*1000)+(int)(Math.random()*100)+(int)(Math.random()*10);
hundrednumber[i]=rand;
if(i<=9){
tennumber[i]=rand;
}else{
for(int j=0;j<=9;j++){
if(tennumber[j]<hundrednumber[i]){
int t=tennumber[j];
tennumber[j]=hundrednumber[i];
hundrednumber[i]=t;
}
}
}
}
}
}
Example 2:若有100亿个整数，请选择出其中最大的10个数。
以上两种思路方向的确是正确的，但如果完全按照以上思路照做，其实是不可行的。假设每个整数在内存中占4个字节，100亿个整数占400亿个字节(B)，1G=109B，400亿B=400*108B=40*10^9B，即40G内存，想象一下，一个程序中的数组就占用了40G的内存，我们的笔记本电脑显然是无法运行这个程序的。所以以上两种思路，我们要做一些调整。调整的方向基于既然一次无法运行这么多的数据，那么纠纷若干次运行即可。
思路一：一次排序只取一定数量，如1000个数进行排序，取出至少前10个数字（注意，必须，至少是十个，否则可能会出错。因为有可能，100亿个数中最大的10个数都在某一次排序中产生，若取数少于10个，则最终的结果一定是错误的。然后把每次排序的前10个数汇聚，继续排序选出前10个即可。当然，此时仍有1亿个数进行排序，占了0.4G内存，我们仍然可以对排序的结果，继续分批排序汇聚。
思路二：步骤1.先把1000个数放入一个数组中，叫做thsoundnumber在创建一个长度为10的空数组，叫做tennumber。
2.将thsoundnumber中的前十个数直接放入tennumber中即可，
3.从第11个数开始，依次与tennnumber中的10个数进行比较，若有比他小的，则替换带入，并把换出的数与余下的数继续进行比较，若发现有较小的数，继续换出以确定最终换出的数一定是原来数组中最小的数。若没有，则tennumber数组不变。
4.再取出1000个数放入thsoundnumber数组，从第一数开始，即重复步骤三，直至100 亿个数执行完毕。
网友评论