题目:给定一个包含 n 个元素的一维线性序列a[p:r],从这 n 个元素中找出第 k 小的元素,1
- 写出算法实现代码并截屏程序运行结果。
- 线性时间选择算法如何解决划分不平衡的问题?
- 分析线性时间选择算法的计算效率。
各位朋友,晚上好!我是小玥,”玥”代表着美好,愿各位好运连连!!!一个人的路很孤独,一群人的路不会孤单,咱们来玥方长!
线性时间选择算法(完整的代码,本题详细解析,附赠随机化划分算法)https://download.csdn.net/download/weixin_51620201/85045879 ;
文章比较详细,文字有点多啦!!!请耐心看完,文末有惊喜!!!!
先思考片刻!1s ,2s,3s,…..1min…………….
好,时间到!!!上思路
目录
一、题目分析
题目给定了一个包含 _n_个元素的一维线性序列 a[0:14]={2,9,11,3,14,7,10,8,15,4,13,1,6,5,12},想要我们求第k小的元素。
注意看,a[0:14]是一个未排序好的数组!那么想要求第k小的元素,我们第一步要干啥?然后呢?接着呢?
第一步:先排序,排成递增数组
第二步:求出结果:a[k]。
嘿,是不是很简单???
问题来了,题目要求我们使用线性时间选择来求解!!!什么是线性时间选择???为什么要用线性时间选择???
别慌,小玥会一一讲解!!!
二、小玥解题
1、假如k=1,或者k=n,需要我们求的第k小元素,对应就是最小值和最大值。
这时只需要顺序查找比较便可直接求解,这很简单!!
public class exam1 {
public static void main(String[] args) //当k=1,k=n时,求数组的最小值和最大值
{
int a[]={2,9,11,3,14,7,10,8,15,4,13,1,6,5,12};
int min=a[0]; //初始化min,max
int max=a[0];
for(int i=0;ia[i+1])
{
min=a[i+1];
a[i]=min;
}
if(max
运行结果:
2、现在咱们的 k=8,数组a[0:14]一共有15个元素,要求第8小元素,就是求数组的中位数!!!
这就要比上面的1难度增大了!!
活学现用,我们可以用我发表过的文章里的方法:快速排序中的partition划分算法。
基本思路:
- 数组a[p:r],选择一个基准元素,默认首元素为基准,base=a[p].
- 开始划分,把比基准base小的元素放在基准的左边,把比基准base大的元素放在基准的右边。
- 返回基准元素的下标j,也就是说,基准元素在原数组中的排位是j+1。
- 把k跟j+1比较,如果k==j+1,那么第k小元素就找到了,即为基准base.
- 如果k
- 直到找到第k小的元素,运行结束!
来人!!!上代码:
public static int partition(int[] a,int p,int r)
{
int x=a[p]; //默认首元素为基准
int i=p,j=r; //i,j为游标
while(true)
{
while(a[i]x && j>=i) //在右边找一个比基准小的元素a[j]
j--;
if(i>=j) //如果i>=j,则不符合交换的条件
break;
Math.swap(a,i,j); //调用交换算法
}
return j; //返回基准的下标
}
上面为partiton划分算法,怎么样!!!
完整的代码:
public class exam2
{
public static int partition(int[] a,int p,int r)
{
int x=a[p]; //默认首元素为基准
int i=p,j=r; //i,j为游标
while(true)
{
while(a[i]x && j>=i) //在右边找一个比基准小的元素a[j]
j--;
if(i>=j) //如果i>=j,则不符合交换的条件
break;
Math.swap(a,i,j); //调用交换算法
}
return j; //返回基准的下标
}
public static int search(int[] a,int p,int r,int k)
{
if(p==r) return a[p];
int i=Partition.partition(a,p,r); //i为基准元素的下标
int j=i-p+1; //j为基准元素在原数组的排位
if(k
运行结果:
经检验,运行结果正确!!!
三、优化解题
partition划分算法分析:
在最好的情况下,默认的首元素为基准刚好就是数组的中位数,那么数组被划分为平衡的两部分,问题规模减少一半,时间复杂度为O(n)。
在最坏的情况下,假如基准刚好是最小值或者最大值,会出现划分不平衡的情况,数组划分后,会出现一个空的数组,问题规模每次只减少了1,时间复杂度为O(n2).
那么,有没有更优化的算法啊?当然有啦!!!partition算法,每次都默认首元素为基准,如果我们设置随机化的基准,那么问题是不是可以解决?
随机化划分算法:randompartition算法,即把基准的设置随机化,在平均情况下,时间复杂度可以达到O(n),这比partition算法跟优化啦!!!
回归题目,让我们使用线性时间选择算法,这算法也是比patition算法更优的,在最坏的情况下,时间复杂度可以达到O(n),也就是题目的题意所在!!!
四、线性时间选择算法
基本思路:
- 数组a[p:r],设置一个阈值,问题规模为n(即为数组的元素个数),当n
- 把原数组划分为n/5组,一般除了最后一组元素不足5个外,其他都满足5个。
- 把每组元素进行冒泡排序,找出中位数,那么一共有n/5个中位数。
- 把n/5个中位数提取出来,再进行冒泡排序,得到”中位数中的中位数”x,作为基准。
- 利用partition划分算法,返回基准x的下标j,并对应计算出x在原数组中的排位i。
- 把k与i比较,如果k
- 返回步骤1,以相同的策略递归找到第k小元素!!!
各位耐心看到这的朋友,是不是觉得这算法难度加大了???别慌,这很正常,越优化的算法,底层的理论都有点深奥,但是细心理解了,那么你就是王者!!!
你看下面,线性时间选择算法,小玥笨笨的弄出来啦!!!
部分代码:
public static void main(String[] args) //线性时间选择算法
{
int[] a=new int[]{2,9,11,3,14,7,10,8,15,4,13,1,6,5,12};
int k=8;
int m=select(a,0,a.length-1,8);
System.out.println("第"+k+"小的元素是"+m);
}
运行结果:
线性时间选择算法(完整的代码,全套资源,附随机化划分算法)https://download.csdn.net/download/weixin_51620201/85045768 ;
完整的线性时间选择算法代码,划分平衡分析以及时间效率公式计算,想要的朋友可以点击上方卡片链接下载哦,有问题随时联系小玥,附赠随机化划分算法randompartition !!!
创作不易,请多多指教!!!Original: https://blog.csdn.net/weixin_51620201/article/details/123779944
Author: 来玥方长
Title: 线性时间选择算法-《数据结构》(结合例题讲解)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/694058/
转载文章受原作者版权保护。转载请注明原作者出处!