从100万个数字中找最大的10个数（提前是元素都是int）？
首先指明原作者：这是《java特种兵》 谢宇 在书本出的一个题，给出了思路，这个思路特别妙。
思路演化阐述：
1、从10个数中找出最大的数？
思路1：先排序啊。
这也是我的第一思路，用冒泡呢？还是 直接插入 还希尔呢？我在脑子转了一圈，在比较那个排序更优。
其实你做了之后发现，这些排序都的循环套循环，时间复杂度O(nxn)。下面给的冒泡排序
package BubbleSort;
/*
* 冒泡排序 从小到大排序
* 2016年7月22日15:00:46
* 唐凌峰
*/
public class BubbleSort2 {
/*
* 从小到大排序 如何让这个算法实现转换成 从大到小呢？ 其实很简单
*/
public void bubbleSortTest(){
int bubble[] ={8,18,4,78,11,96,88,99};
for(int i=0;i<bubble.length;i++){
for(int j=0;j<bubble.length-i-1;j++){
//比较相邻两个元素的大小,一定要相邻元素比较，为什么原理就只这样的。
if (bubble[j+1]>bubble[j]){
int temp =bubble[j];
bubble[j]=bubble[j+1];
bubble[j+1]=temp;
};
}
};
//打印出排序好的数组
for(int i=0;i<bubble.length;i++){
System.out.println("Index: "+i+" value: "+bubble[i]);
}
}
public static void main(String[] args){
BubbleSort2 bubbleSort= new BubbleSort2();
bubbleSort.bubbleSortTest();
}
}
思路2: 假设第一个元素就是最大。
再遍历以后的9个元素，跟第一个比，比第一大就交互。这样的时间复杂度就是O(n)。
请看下面代码:
package MaxAndMin;
/*
* 查找最大值
* 时间：2016年7月30日19:12:47
* 编辑：唐凌峰
*/
public class FindMax {
public static void findMaxTest1(){
int[] arrayTest1=new int[]{100,4564,333333,666,9999,5,66,89,77,99,22};
//假设第一个是最大的或最小的
int minValue=arrayTest1[0];
for(int i=1;i<arrayTest1.length;i++){
if(arrayTest1[i]>minValue){
minValue=arrayTest1[i];
}
};
System.out.print(minValue);
}
public static void main(String[] args){
FindMax.findMaxTest1();
}
}
这样不用排序也能找出最大的，而且性能提高了，是不是能妙。
2、如何从100万个元素中找出10最大的元素？
思路1：还先排序，不用了吧，我们模仿从10元素个中找最大的。那个中不用排序的思路。
假设这100万个无序序列的前10个元素是最大 。
从i=10开始遍历这100万个元素，跟前面的10个元素比较，只要比这个10个元素中的任何一个大就交换
请看下面代码实现：
package MaxAndMin;
/*
* 从100万无序数中，找出最大的10个 int取值范围： -2147483648～2147483647
* 唐凌峰
* 2016年7月30日17:03:43
* 这个时间复杂度虽然是o(nxn) 其实比排序快多了 排序是100万x 100万 这个只有 10x100万。一下性能提高了10万倍！
*/
public class FindTenMax {
public static void findTenNode(){
int[] arrayNode=new int[]{11,4,515,55,66,111,71,77,99,22,222,123,345,7899,124,156,167,1677,176,178,189,999,10000,11111,7777,788787,168888};
//假定前10个数是最大的，然后拿后面的元素更这10个元素一一对比，只要比其中任何一个大就换进去
int[] arrayAssume={11,4,515,55,66,111,71,77,99,22};
for(int i=10;i<arrayNode.length;i++){
for(int j=0;j<arrayAssume.length;j++){
if(arrayNode[i]>arrayAssume[j]){
int temp =arrayAssume[j];
arrayAssume[j]=arrayNode[i];
arrayNode[i]=temp;
}
}
}
for(int k=0;k<10;k++){
System.out.print(""+arrayAssume[k]+",");
}
}
public static void main(String[] args){
FindTenMax.findTenNode();
}
}
这样表面上看时间复杂度还是O() 其实你指向看这样做的计算机值最坏的时候了 就：10x100万步
如果你先排序，就是：100万x100万步。
性能一下提升了 10万倍，如果只找最大的5个，性能提高的可不是10万倍
思路决定出路，现在对这话，理解的更有感悟。
这里面思路妙在：假设 假设。
其实想想我们的直接插入排序，类似用的这个思路。
记得以前在铁科院给动车做的一个项目，每张表的数据至少100万以上。现在看来有些地方可以深度优化的。