Java基于分治算法实现的线性时间选择操作示例
本篇章节讲解Java基于分治算法实现的线性时间选择操作。分享给大家供大家参考,具体如下: 线性时间选择问题:给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素,(这里给定的线性集是无序的)。 随机划分线性选择 线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分,与快速排序不同的是,它只对划分出的子数组之一进行递归处理。 程序解释:利用随机函数产生划分基准,将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r],使a[p:i]中的每个元素都不大于a[i+1:r]中的每个元素。接着"j=i-p+1"计算a[p:i]中元素个数j.如果k<=j,则a[p:r]中第k小元素在子数组a[p:i]中,如果k>j,则第k小元素在子数组a[i+1:r]中。注意:由于已知道子数组a[p:i]中的元素均小于要找的第k小元素,因此,要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。 在最坏的情况下,例如:总是找到最小元素时,总是在最大元素处划分,这是时间复杂度为O(n^2)。但平均时间复杂度与n呈线性关系,为O(n) package math; import java.util.Scanner; import java.util.Random; public class RandomSelect { public static void swap(int x,int y) { int temp = x; x = y; y = temp; } public int Random (int x,int y) { Random random = new Random(); int num = random.nextInt(y)%(y - x + 1) + x; return num; } public int partition(int[] list,int low,int high) { int tmp = list[low]; //数组的第一个作为中轴 while (low < high) { while (low < high && list[high] > tmp) { high--; } list[low] = list[high]; //比中轴小的记录移到低端 while (low < high && list[low] < tmp) { low++; } list[high] = list[low]; //比中轴大的记录移到高端 } list[low] = tmp; //中轴记录到尾 return low; //返回中轴的位置 } public int RandomizedPartition (int[] arrays,int left,int right) { int i = Random(left,right); swap(arrays[i],arrays[left]); return partition(arrays,left,right); } public int RandomizedSelect(int[] arrays,int right,int k) { if(left == right ) { return arrays[left]; } int i = RandomizedPartition(arrays,right); int j = i - left + 1; if(k <= j) { return RandomizedSelect(arrays,i,k) ; } else { return RandomizedSelect(arrays,i+1,right,k-j); } } public static void main(String args[]) { System.out.println("编程小技巧测试结果:"); int[] a = {7,5,3,4,8,6,9,1,2}; for (int i = 0; i < 9; i ++) { System.out.print(a[i]+ " "); } System.out.println(); RandomSelect r = new RandomSelect(); System.out.println("你要查询的元素是数组中第几小的?"); @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = r.RandomizedSelect(a,m); System.out.println("这个数组中第" + m + "小的元素是:"+ n); } } 运行结果: 更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》 希望本文所述对大家java程序设计有所帮助。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |