歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

最壞情況線性時間的選擇 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. }  
Copyright © Linux教程網 All Rights Reserved