算法设计与分析作业--线性时间选择

 import java.util.Random;
import java.util.Scanner;

public class xianxingshijanxuanze {
 static Random ran=new Random();
 public static void main(String[] args) {
  int a[]= {1,3,34,56,23,69,46,11,35,5,32,26,45};
  Scanner s=new Scanner(System.in);
  System.out.println("请选择第几小的数");
  int x=s.nextInt();
  
  System.out.println("第"+x+"小的数为："+RandomizedSelect(a,0,12,x));
  }
 
 public  static int RandomizedSelect(int a[],int p,int r,int k) {
   if(p==r)return a[p];
   int i=Randomizedpartition(a,p,r);
   int j=i-p+1;
   if(k<=j)return  RandomizedSelect(a, p,i,k);
   else return  RandomizedSelect(a, i+1,r,k-j); 
  }
 private static int Randomizedpartition(int a[],int p,int r) {
  int i=ran.nextInt(r);
  swap(a,i,p);
  return partition(a,p,r);
 }
 
 public static  int partition(int [] a,int p, int r) {
  int i=p;
     int j=r+1;
     int  x=a[p];
     while(true) {
      while(a[++i]x);    
      if(i>=j) break;
      swap(a,i,j);
      
     }
     a[p]=a[j];
     a[j]=x;
     return j;
 }
 public static void swap(int[] a,int i,int j) {
     int  temp= a[i];
  a[i]=a[j];
  a[j]=temp;
 }
 
}