求数组中的K大数,快排思想(Java改…

package cn.edu.nwsuaf.cie.qhs; import java.util.Random; import java.util.Scanner; // // * // * @author 静寞小森(沧海森林) // * Our goal is to get the number which is bigger than other k. // * So we program this program to reach our goal. // * // 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)+start; ? ? ? ? ? ? int i = start-1; ? ? ? ? ? ? int j = start; ? ? ? ? ? ? System.out.println("index="+index+";start="+start+";length="+length); ? ? ? ? ? ? this.swap(index,start+length-1); ? ? ? ? ? ? for(j=start;j<start+length;j++){ ? ? ? ? ? ? ? ? ? if(initArray[j] < initArray[start+length-1]){ ? ? ? ? ? ? ? ? ? ? ? ? this.swap(++i,j); ? ? ? ? ? ? ? ? ? ? ? ? System.out.println("i="+i+";j="+j); ? ? ? ? ? ? ? ? ? } ? ? ? ? ? ? } ? ? ? ? ? ? this.swap(++i,start+length-1); ? ? ? ? ? ? System.out.println("i="+i+";start+length-1="+(start+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 -2; ? ? ? ? ? ? mid = this.random_partion(start,length); ? ? ? ? ? ? if ((mid-start) == length-k){System.out.println("----->this is the first!!!!!"); return initArray[mid];} ? ? ? ? ? ? else if((mid-start) < length-k){System.out.println("----->this is the second!!!!!");? return getMaxK(mid+1,length-mid+start-1,k);} ? ? ? ? ? ? else{System.out.println("----->this is the third!!!!!");? return getMaxK(start,mid-start,k-(length-mid+start));} ? ? ? } ? ? ? ? ? ? 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 = {12012,3,945,965,66,232,65,7,8,898,56,878,170,13,5}; ? ? ? ? ? ? int length; ? ? ? ? ? ? int K = 9; //? ? ? ? ? ? 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); ? ? ? } }