1 package test;
 2 import java.util.Random;
 3 /**
 4  * 线性时间选择问题：找出一个包含n个元素的集合中的第K小的元素
 5  */
 6 public class LinerSelect {
 7 
 8     /**
 9      * @param args
10      */
11     public static void main(String[] args) {
12         
13         int[] elements={1,5,2,5,8,45,15,26};
14         int b=KthMin(elements, 0, 7, 3);
15         System.out.print("第三小的元素为："+b);
16     }
17     //寻找第k小的元素
18     public static int KthMin(int[] elements,int start,int end,int k)
19     {
20         if(start==end)return elements[start]; 
21         int i=index(elements, start, end);
22         int j=i-start+1;//统计比随机基准值小的元素个数
23         if(k<=j)
24             return KthMin(elements, start, i, k);
25         else {
26             return KthMin(elements, i+1, end, k-j);
27         }
28     }
29     //随机将集合中的元素分为两部分，中间元素。     
30     private static int index(int[] elements,int start,int end)
31     {
32         Random random=new Random();
33         int i=random.nextInt(end-start+1)+start;
34         swap(elements, i, start);
35         return Partition(elements, start, end);
36     }
37     //以第一个元素为基准值将集合分为左右两部分
38     private static int Partition(int[] a,int start,int end)
39     {
40         //i为从开头比较的元素下标，j为从末尾开始的元素下标
41         int i=start+1,j=end;
42         int key=a[start];
43         while(true)
44         {
45             while(a[i]<key&&i<end)
46             {
47                 i++;
48             }
49             while(a[j]>key)
50             {
51                 j--;
52             }
53             if(i>=j)
54                 break;
55             swap(a, i, j);
56         }
57         a[start]=a[j];
58         a[j]=key;
59         return j;
60         
61     }
62     private static void swap(int[] a,int i,int j)
63     {
64         int temp=a[i];
65         a[i]=a[j];
66         a[j]=temp;
67     }
68 }