经典算法:快速选择算法
前言
快速选择算法是一种选择算法,用于在无序列表中查找第K个最小元素。这个算法和快速排序算法有关。它在实际应用是一种高效的算法,具有很好的平均时间复杂度,最坏的时间复杂度非常不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。
例如:
输入: [7, 4, 6, 3, 9, 1] k = 2
输出: 第 k' 个最小的数组元素是 3
输入: [7, 4, 6, 3, 9, 1] k = 1
输出: k'第一个最小的数组元素是 1
快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。
但是,不像在快速排序中那样递归到两侧,快速选择算法只递归到带有搜索元素的一侧。由于中心处于其最终排序位置,因此在它之前的所有那些都以未排序的顺序,而在它之后的所有那些都以未排序的顺序。
这将平均情况复杂度从O(n.log(n))降低到O(n),最坏情况为O(n 2 ),其中n
是输入的大小。
与快速排序一样,快速选择一般是以原地算法的方式实现,除了选出第k小的元素,数据也得到了部分地排序。
Java示例
import java.util.Arrays;
class GFG {
public static int partition(int[] arr, int low,
int high)
{
int pivot = arr[high], pivotloc = low;
for (int i = low; i <= high; i ) {
if (arr[i] < pivot) {
int temp = arr[i];
arr[i] = arr[pivotloc];
arr[pivotloc] = temp;
pivotloc ;
}
}
//将支点交换到最终的支点位置
int temp = arr[high];
arr[high] = arr[pivotloc];
arr[pivotloc] = temp;
return pivotloc;
}
public static int kthSmallest(int[] arr, int low,
int high, int k)
{
// 找到分区
int partition = partition(arr, low, high);
// 如果分区值等于第 k 个位置,则返回 k 处的值。
if (partition == k - 1)
return arr[partition];
// 如果分区值小于第 k 个位置,则搜索数组的右侧。
else if (partition < k - 1)
return kthSmallest(arr, partition 1, high, k);
// 如果分区值大于第 k 个位置,则搜索数组的左侧。
else
return kthSmallest(arr, low, partition - 1, k);
}
public static void main(String[] args)
{
int[] array = new int[] { 10, 4, 5, 8, 6, 11, 26 };
int[] arraycopy
= new int[] { 10, 4, 5, 8, 6, 11, 26 };
int kPosition = 3;
int length = array.length;
if (kPosition > length) {
System.out.println("索引超出范围");
}
else {
// 找到第 k 个最小值
System.out.println(
"第K个最小的元素是 : "
kthSmallest(arraycopy, 0, length - 1,
kPosition));
}
}
}
输出:第K个最小的元素是6
时间复杂度
与快速排序类似,快速选择算法在平均状况下有着不错的表现,但是对于基准值的选择十分敏感。如果基准值选择上佳,搜索范围每次能够指数级减少,这样一来所耗时间是线性的(即O(n))。
但如果基准值选择非常不好,使得每次只能将搜索范围减少一个元素,则最糟的总体时间复杂度是平方级的(O(n^2)):例如对一个升序排列的数组搜索其最大值,而每次都选择第一个元素作为基准值。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanfbebi
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01