*题目：给定一个包含n个元素的一维线性序列a[p:r]，从这n个元素中找出第k小的元素，1<=k<=n。设a[0:14]={2,9,11,3,14,7,10,8,15,4,13,1,6,5,12}，k = 8，采用线性时间选择算法解决该问题。*
- 写出算法实现代码并截屏程序运行结果。
- 线性时间选择算法如何解决划分不平衡的问题？
- 分析线性时间选择算法的计算效率。
各位朋友，晚上好！我是小玥，”玥“代表着美好，愿各位好运连连！！！一个人的路很孤独，一群人的路不会孤单，咱们来玥方长！
线性时间选择算法（完整的代码，本题详细解析，附赠随机化划分算法）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;i<a.length-1;i++) //数组遍历
{
if(min>a[i+1])
{
min=a[i+1];
a[i]=min;
}
if(max<a[i+1])
{
max=a[i+1];
a[i]=max;
}
}
System.out.println("最小的元素为："+min);
System.out.println("最大的元素为："+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<j+1，那么说明要求的元素在数组的左边，返回第1步骤，划分a[p:j-1];如果是k>j+1,那么说明要求的元素在数组的右边，返回第1步骤，划分a[j+1,r].
- 直到找到第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 && i<j) //在左边找一个比基准大的元素a[i]
i++;
while(a[j]>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 && i<j) //在左边找一个比基准大的元素a[i]
i++;
while(a[j]>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<=j) return search(a,p,i,k);
else return search(a,i+1,r,k-j);
}
public static void main(String[] args)
{
int a[]={2,9,11,3,14,7,10,8,15,4,13,1,6,5,12};
int result=search(a,0,a.length-1,8);
System.out.println("第8小的元素为："+result);
}
}
运行结果：
** 经检验，运行结果正确！！！**
三、优化解题
partition划分算法分析：
在最好的情况下，默认的首元素为基准刚好就是数组的中位数，那么数组被划分为平衡的两部分，问题规模减少一半，时间复杂度为O(n)。
在最坏的情况下，假如基准刚好是最小值或者最大值，会出现划分不平衡的情况，数组划分后，会出现一个空的数组，问题规模每次只减少了1，时间复杂度为O(n2).
那么，有没有更优化的算法啊？当然有啦！！！partition算法，每次都默认首元素为基准，如果我们设置随机化的基准，那么问题是不是可以解决？
随机化划分算法：randompartition算法，即把基准的设置随机化，在平均情况下，时间复杂度可以达到O（n)，这比partition算法跟优化啦！！！
** 回归题目，让我们使用线性时间选择算法，这算法也是比patition算法更优的，在最坏的情况下，时间复杂度可以达到O(n)，也就是题目的题意所在！！！**
四、线性时间选择算法
基本思路：
- ** 数组a[p:r],设置一个阈值，问题规模为n(即为数组的元素个数），当n<5时，问题规模很小，可以直接使用冒泡排序求解问题，否则转到步骤2.（其实，n<5设置还不是最优的，正常设置n<75，当考虑到本问题规模为15，比较小，为了应用上本算法，故设置为n<5）。**
- 把原数组划分为n/5组，一般除了最后一组元素不足5个外，其他都满足5个。
- 把每组元素进行冒泡排序，找出中位数，那么一共有n/5个中位数。
- 把n/5个中位数提取出来，再进行冒泡排序，得到“中位数中的中位数”x，作为基准。
- 利用partition划分算法，返回基准x的下标j，并对应计算出x在原数组中的排位i。
- 把k与i比较，如果k<=i,那么我们要求的第k小元素肯定在a[p:j]中，否则在a[j+1:r]中.
- 返回步骤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 ！！！
创作不易，请多多指教！！！
版权归原作者 来玥方长 所有， 如有侵权，请联系我们删除。