求数组中的K大数（时间复杂度控制…

【源码】 package cn.edu.nwsuaf.cie.qhs; import java.util.Random; import java.util.Scanner; public class GetGreateK { ? ? ? private int initArray[]; ? ? ? public int[] getInitArray() { ? ? ? ? ? ? return initArray; ? ? ? } ? ? ? public void setInitArray(int[] initArray) { ? ? ? ? ? ? this.initArray = initArray; ? ? ? } ? ? ? public GetGreateK(){} ? ? ? public GetGreateK(int[] array){ ? ? ? ? ? ? this.initArray = array; ? ? ? } ? ? ? public int random_partion(int start,int length){ ? ? ? ? ? ? Random rand = new Random(); ? ? ? ? ? ? int index = rand.nextInt(length); ? ? ? ? ? ? int i = start-1; ? ? ? ? ? ? int j = start; ? ? ? ? ? ? this.swap(index,length-1); ? ? ? ? ? ? for(j=start;j<length;j++){ ? ? ? ? ? ? ? ? ? if(initArray[j] < initArray[length-1]){ ? ? ? ? ? ? ? ? ? ? ? ? this.swap(++i,j); ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? } ? ? ? ? ? ? this.swap(++i,length-1); //? ? ? ? ? ? System.out.println("------>"+i); ? ? ? ? ? ? return i; ? ? ? } ? ? ? public int getMaxK(int start,int length,int k){ ? ? ? ? ? ? int mid; ? ? ? ? ? ? if (k<=0) return -1; ? ? ? ? ? ? if (length<k) return -1; ? ? ? ? ? ? mid = this.random_partion(start,length); ? ? ? ? ? ? if (mid == length-k) return initArray[mid]; ? ? ? ? ? ? else if(mid < length-k) return getMaxK(start+mid+1,length-mid-1,k); ? ? ? ? ? ? else return getMaxK(start,mid,k-(length-mid)); ? ? ? } ? ? ? ? ? ? public void swap(int a,int b){ ? ? ? ? ? ? int temp = initArray[a]; ? ? ? ? ? ? initArray[a] = initArray[b]; ? ? ? ? ? ? initArray[b] = temp; ? ? ? } ? ? ? ? ? ? public static void main(String[] args) { ? ? ? ? ? ? // TODO Auto-generated method stub ? ? ? ? ? ? //12012? 3? 945? 965? 66? 232? 65? 7? 8? 898? 56? 878? 170? 13? 5 ? ? ? ? ? ? int[] array; ? ? ? ? ? ? int length; ? ? ? ? ? ? int K; ? ? ? ? ? ? Scanner scanner = new Scanner(System.in); ? ? ? ? ? ? System.out.println("请输入数组长度："); ? ? ? ? ? ? length = scanner.nextInt(); ? ? ? ? ? ? array = new int[length]; ? ? ? ? ? ? for(int i = 0; i < length;i++){ ? ? ? ? ? ? ? ? ? System.out.println("请输入第"+(i+1)+"个数："); ? ? ? ? ? ? ? ? ? array[i] = scanner.nextInt(); ? ? ? ? ? ? } ? ? ? ? ? ? System.out.println("请输入K："); ? ? ? ? ? ? K = scanner.nextInt(); ? ? ? ? ? ? GetGreateK kth = new GetGreateK(); ? ? ? ? ? ? kth.setInitArray(array); ? ? ? ? ? ? int maxK = kth.getMaxK(0,array.length,K); ? ? ? ? ? ? System.out.println("maxK---->"+maxK); ? ? ? } }