最壞情況線性時間的選擇 Java實現

最壞情況線性時間的選擇 Java實現：

1. package ctgu.sugite.content.character09;
3. import java.util.Arrays;
4. import java.util.Random;
6. public class WorstLinearSelect {
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. }
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. }
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. }
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. }
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. }