（转载请注明出处：http://blog.csdn.net/buptgshengod）
题目介绍
在n个数中取第k大的数（基础篇），之所以叫基础篇是因为还有很多更高级的算法，这些以后再讨论。本文用两种最基本的方法来解决这个问题。使用java语言描述。例子是十个数中取第三大的。
算法一
用冒泡法将n个数从大到小排序，再取第k大。
public class test {
public static void main(String []args)
{
int i,j;
final int n=10;
final int k=3;
boolean flag=true;
int[] list=new int[n];
System.out.print("十个数里第三大的数");//题目
System.out.println(); //换行
for(i=0;i<10;i++)
{
list[i]=(int) (Math.random()*100);//随机生成100以内十个数
System.out.print(list[i]+",");
}
for(j=0;j<list.length-1;j++)
{
for(i=0;i<list.length-1;i++)
{
if(list[i]>=list[i+1])
{}
else
{
int m=list[i];
list[i]=list[i+1];
list[i+1]=m;
}
}
}
System.out.println(); //换行
for(i=0;i<10;i++)
{
System.out.print(list[i]+",");
}
System.out.println(); //换行
System.out.print("答案是"+list[k-1]);
}
}
显示结果
算法二
先取k个数，将他们排序。再从剩下的n-k个数中取数与k个数中最小的比较，如果比k个数最小的大，则替代最小的数。以此类推。
public class Test {
public static void main(String[] args)
{
int i,j,m;
final int n=10;
final int k=3;
int[] list=new int[n];
System.out.print("十个数取第三大");//题目
System.out.println();//换行
for(i=0;i<list.length;i++)
{
list[i]=(int) (Math.random()*100);
System.out.print(list[i]+",");
}
/*
* 取数组前三个数，将其按冒泡法从大到小排序
*/
for(j=0;j<k-1;j++)
{
for(i=0;i<k-1;i++)
{
if(list[i]>=list[i+1])
{}
else
{
int t=list[i];
list[i]=list[i+1];
list[i+1]=t;
}
}
}
for(i=k;i<n;i++)
{
if(list[k-1]>=list[i])
{}
else
{
list[k-1]=list[i];
for(j=0;j<k-1;j++)
{
for(m=0;m<k-1;m++)
{
if(list[m]>=list[m+1])
{}
else
{
int t=list[m];
list[m]=list[m+1];
list[m+1]=t;
}
}
}
}
}
System.out.println();
System.out.print("第三大的是"+list[k-1]);
}
}
显示结果
