1 import java.util.Random; 2  3  4 public class K_Max { 5  6     /** 7      * @param args 8      */ 9     //求第K大的数，保证K大于等于1，小于等于array.length/2哦10     public static int TopK(int array[],int K)11     {12         int topk[] = new int [K];13         for(int i = 0; i<topk.length;i++)14             topk[i] = array[i];15         16         InsertSort(topk);//从小到大17         18         for(int i = topk.length; i<array.length;i++)19         {20             int target = array[i];21             if(target < topk[0])22                 ;23             else24             {25                 int position = findInsertPlace(topk,target,0,topk.length-1);26                 for(int j = 0;j<position;j++)27                     topk[j] = topk[j+1];28                 topk[position] = target;29             }    30         }31         return topk[0];32     }33     //二分查找应该插入的位置34     public static int findInsertPlace(int [] A,int target,int a, int b)35     {   36         int  middle = a+(b-a)/2;37         if(a>b)38             return b;39         else if (A[middle]==target)40             return middle;41         else if (A[middle]< target)42             return findInsertPlace(A,target,middle+1,b);43         else 44             return findInsertPlace(A,target,a,middle-1);45     }46     //插入排序47     public static void InsertSort(int [] num)//从小到大排序48     {49         for(int i =1; i<num.length;i++)50         {   51             int temp = num[i];52             int j=i-1;53             while(j>=0 && temp < num[j])54             {55                 num[j+1]=num[j];56                 j--;57             }58             num[j+1] = temp;59         }60        61     }62     public static void main(String[] args) {63         //随机赋值一个数组64         int randomArray[] = new int[15];65         Random random = new Random();66         for(int i = 0; i < randomArray.length;i++) {67             randomArray[i] = Math.abs(random.nextInt()%(randomArray.length*10));68         }69         int K =3;70         int k_max = TopK(randomArray,K);71         System.out.println("The "+K +" th biggest number of:");72         InsertSort(randomArray);73         for(int a:randomArray)74             System.out.print(a+" ");75         System.out.println();76         System.out.println("is: "+k_max);77     }79 }