个人网站设计与制作代码,海外网站速度慢,自己怎样做免费网站,东莞短视频seo优化减治法在查找算法中的应用
快速查找#xff1a;选择问题是求一个n个数列表的第k个最小元素的问题#xff0c;这个数k被称为顺序统计量。对于k1或kn来说#xff0c;这并没有什么意义#xff0c;我们通常会要找出这样的元素#xff1a;该元素比列表中一半元素大#xff0…减治法在查找算法中的应用
快速查找选择问题是求一个n个数列表的第k个最小元素的问题这个数k被称为顺序统计量。对于k1或kn来说这并没有什么意义我们通常会要找出这样的元素该元素比列表中一半元素大比另一半元素小这样的元素被称为中值。我们当然可以对列表进行排序之后找出对应下标的值但是这样一个查找问题反而要对整个列表排序是不是有点多余了呢
这里引入划分的概念我们可以标定一个枢轴任意元素一般为首个元素使得左半部分元素均小于枢轴右半部分均大于枢轴。划分的方法由两种Lomuto划分和Hoare划分。这里仅介绍Lomuto。
我们假设有一个数组a[0, n-1],其子数组为a[l, r](0 l r n-1),假定首个元素为枢轴p将该数组分为三段顺序放在p之后依次为第一段[元素小于p]第二段[元素大于等于p]第三段[尚未处理元素]。算法开始时前两段均为空。
从i l1开始从左到右扫描子数组a[l, r],将第三段的首个元素与p比较若a[i]p执行i1这就相当于将a[i]划入了第二段同时缩小了第三段若a[i]p需要将s1(s始终指向第一段的末位元素)同时交换a[i]与a[s]之后i1。直到第三段为空交换a[p]与a[s]。
下图为Lomuto划分示意图 熟悉快速排序的读者估计看出来了这就是快速排序中的一部分函数只不过没有接触过Lomuto这种叫法而已。
当然我们这里使用的方法就是快速选择(“快速”这一方法一开始并非用于排序而是查找)下面给出查找第k小元素的代码 public class Main {static int[] a {89, 45, 68, 90, 29, 34, 17};static int k 2;public static void main(String[] args) {System.out.println(fastsort(0, a.length-1, k));for (int i 0; i a.length; i) {System.out.print(a[i] );}}private static int Lomuto(int l, int r) {int p a[l];int s l;for (int i l1; i r; i) {if (a[i] p) {s s1;int temp a[s];a[s] a[i];a[i] temp;}}int temp a[l];a[l] a[s];a[s] temp;return s;}private static int fastsort(int l, int r, int k) {int s Lomuto(l, r);/*** s在划分之后变成了枢轴所在的位置下标如果sk,输出a[s]* 这里要写成lk-1如果划分到右侧只写k会出问题* */if (s l k - 1) {return a[s];}else if (s l k - 1){return fastsort(l, s-1, k);} else {return fastsort(s1, r, lk-1-s);}}
}
不幸的是这样的算法时间复杂度为O(n^2)比之前基于排序的方法实际上更糟糕但是分析表明这种方法的平均情况下效率是线性的。而且基于划分的算法不仅可以查找第k小的元素还可以给出列表中k个最小元素和n-k个最大元素。
