最坏情况线性时间的选择 Java实现

最坏情况线性时间的选择 Java实现

最坏情况线性时间的选择 Java实现：

1. package ctgu.sugite.content.character09;  
2.   
3. import java.util.Arrays;  
4. import java.util.Random;  
5.   
6. public class WorstLinearSelect {  
7.   
8.     public static void main(String[] args) {  
9.         int n = 34, k = 7;/* 34个元素中找出第7小的元素 */  
10.         int[] a = new int[n];  
11.         Random rd = new Random();  
12.         for (int i = 0; i < n; i++) {  
13.             a[i] = rd.nextInt(100);  
14.         }  
15.         System.out.println(Arrays.toString(a));  
16.         System.out.println(select(a, 0, n - 1, k));/* 进行线性查找 */  
17.         Arrays.sort(a);  
18.         System.out.println(Arrays.toString(a));/* 排序后输出，进行验证 */  
19.     }  
20.   
21.     private static int select(int[] a, int law, int high, int k) {  
22.         if (high - law < 5) {  
23.             insertSort(a, law, high);  
24.             return a[law + k - 1];  
25.         }  
26.         int teams = (high - law + 5) / 5;// 组数   
27.         for (int i = 0; i < teams; i++) {  
28.             /* 第一步：将输入数组的n个元素划分为n/5组，每组5个元素，且至多只有一个组由剩下的n mod5个元素组成 */  
29.             int left = law + i * 5;  
30.             int right = (law + i * 5 + 4) > high ? high : law + i * 5 + 4;  
31.             int mid = (left + right) / 2;  
32.             /* 第二步：寻找(n+4)/5个组中每一组的中位数。首先对每组中的元素（至多为5个）进行插入排序，然后从排序过的序列中选出中位数 */  
33.             insertSort(a, left, right);  
34.             swap(a, law + i, mid);// 将中位数置前   
35.         }  
36.         /* 第三步：对第二步中找出的(n+4)/5个中位数，递归调用select以找出其中位数x */  
37.         int pivot = select(a, law, law + teams - 1, (teams + 1) / 2);  
38.         /* 第四步：利用修改过的partition过程，按中位数的中位数x对输入数组进行划分 */  
39.         int pos = partition(a, law, high, pivot);  
40.         /* 第五步：判断pos位置是否为要找的数，若不是则在低区或者高区递归select */  
41.         int leftNum = pos - law;  
42.         if (k == leftNum + 1)  
43.             return a[pos];  
44.         else if (k <= leftNum)  
45.             return select(a, law, pos - 1, k);  
46.         else  
47.             return select(a, pos + 1, high, k - leftNum - 1);  
48.     }  
49.   
50.     private static int partition(int[] a, int law, int high, int pivot) {  
51.         int index = law;  
52.         for (int i = law; i <= high; i++) {  
53.             if (a[i] == pivot) {  
54.                 index = i;  
55.                 break;  
56.             }  
57.         }/* 找到枢纽的位置 */  
58.         swap(a, index, high);  
59.         int i = law - 1;  
60.         for (int j = law; j < high; j++) {  
61.             if (a[j] <= pivot) {  
62.                 swap(a, j, ++i);  
63.             }  
64.         }  
65.         swap(a, high, ++i);  
66.         return i;  
67.     }  
68.   
69.     private static void swap(int[] a, int i, int j) {  
70.         int temp = a[i];  
71.         a[i] = a[j];  
72.         a[j] = temp;  
73.     }  
74.   
75.     /* 插入排序 */  
76.     private static void insertSort(int[] a, int law, int high) {  
77.         for (int i = law + 1; i <= high; i++) {  
78.             int key = a[i];  
79.             int j = i - 1;  
80.             while (j >= law && a[j] > key) {  
81.                 a[j + 1] = a[j];  
82.                 j--;  
83.             }  
84.             a[j + 1] = key;  
85.         }  
86.     }  
87. }