从数组中选择第k大的数

package gxu.jsj.wyg;

public class Select {
 public static void main(String[] args) {
  int[] a = {1,5,8,-4,9,6,3,-1,4,7};
  //SortSelect.sort(a);
  SortSelect.show(a);
  int k = 6;
  SortSelect.select_k(a, 0, a.length, k);
  SortSelect.show(a);
  System.out.printf("第%d大的数为：%d\n",k,SortSelect.K_Num);
 }
}

class SortSelect {
 public static int K_Num;
 
 //使用冒泡排序算法，对数组进行排序
 public static void sort(int[] a) {
  int i,j;
  int len = a.length;
  for(i=0; i<len-1; i++) {
   for(j=i+1; j<len; j++) {
    if(a[i] < a[j]) {
     swap(a,i,j);
    }
   }
  }
 }
 
 //从a中选择第k大元素,从排好序的数组中进行选择
 public static int select_k(int[] a,int k) {
  if(k >= a.length) return -10000;
  sort(a);
  
  return a[k];
 }
 
 //从未排序的数组中进行选择第k大元素,基于快速排序算法
 public static void select_k(int[] a,int start,int end,int k) {   
  int m = partation(a, start, end);  
  int index = k - 1;  
  if(index == m) { 
   K_Num = a[m];
   return;
  }else if(index < m) {
   select_k(a,start,m,k);
  } else {
   select_k(a,m+1,end,k);
  } 
 }
 
 private static int partation(int[] a,int start,int end) {
  
  int s = start;
  int t = end-1;
  int k = a[start];
  
  while(s < t) {
   while(k >= a[t] && s < t) 
    t --;
   if(s<t) swap(a,s,t);
   
   while(k <= a[s] && s < t) 
    s ++;
   if(s<t) swap(a,s,t);   
  }
  return s;
 }
 
 public static void swap(int[] a,int x,int y) {
  int temp = a[x];
  a[x] = a[y];
  a[y] = temp;
 }
 
 public static void show(int[] a) {
  for(int i=0; i<a.length; i++) {
   System.out.printf("%d ",i+1);
  }
  System.out.println();
  for(int i=0; i<a.length; i++) {
   System.out.printf("%d ",a[i]);
  }
  System.out.println();
 }
}