在一列数中求第k大的数字
这个题目的一种思路是利用快排思想来解决，可以达到O（nlogn）的时间效率。
详细代码如下：
/* * 在一列数中寻找第k大的数，使用快排思想，一趟快排后会返回一个基准点的位置，如果该位置loc正好处于 * 要求的第k个数的位置，则该位置的数即为所求；如果loc>k，说明要求的第k大的数，在左边子数组中，如果loc<k， * 则要求的数为右边子数组的第k-loc个位置的数 */public class Findnth {public static void main(String args[]){int array[] = {5, 6, 7, 9, 8, 4, 3, 2, 1, 10, 12, 11, 13, 14, 15, 16, 17, 19, 18, 20} ;int re=select(array,0,array.length-1,15);System.out.println("第---小的数是："+re);}public static int select(int a[],int left,int right,int k){//求第k小的数if(left==right){return a[left];}int loc=partition(a,left,right);//返回一趟快排后某个基准点的位置int kth=loc-left+1;//该基准数在当前的子数组中是第几小的数if(k==kth){//如果该趟排序后返回的基准位置所处的位置正好是这个子数组的第k小的数return a[loc];//返回处于该位置的值就是要求的第k小的数}else if(k<kth){return select(a,left,loc-1,k);//求左边子数组中的第k小的数}else{return select(a,loc+1,right,k-kth);//求右边子数组中的第k-kth小的数}}public static int partition(int a[],int left,int right){//一趟快排，返回以a[left]为基准点的位置int temp=a[left];while(left<right){while(left<right&&a[right]>=temp){right--;}a[left]=a[right];while(left<right && a[left]<=temp){left++;}a[right]=a[left];}a[left]=temp;return left;}}? 1 楼 albrich 2012-02-29 你是怎么想出来的，太厉害了，我有点看不懂 2 楼 albrich 2012-02-29 我又仔细看了一下这个方法不太对，int [] n={1,23,12,12,12,58,24,44,32,56,56,56,67,23,44};