Welcome 微信登录
编程资源 图片资源库 蚂蚁家优选 PDF转换器 软件资源

软件开发、小程序制作、系统集成与运维、空间租用、硬件开发、视频监控、技术咨询与支持——联系电话：0311-88999002/88999003

首页 / 操作系统 / 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. }  
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图