线性时间选择算法-《数据结构》（结合例题讲解）

题目：给定一个包含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，采用线性时间选择算法解决该问题。

1. 写出算法实现代码并截屏程序运行结果。
2. 线性时间选择算法如何解决划分不平衡的问题？
3. 分析线性时间选择算法的计算效率。

各位朋友，晚上好！我是小玥，”玥“代表着美好，愿各位好运连连！！！咱们来玥方长！

文章比较详细，文字有点多啦！！！请耐心看完，文末有惊喜！！！！

先思考片刻！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<a[i+1])     {  max=a[i+1];  a[i]=max;     } } System.out.println("最小的元素为："+min); System.out.println("最大的元素为："+max);    } }

1. 数组a[p:r],选择一个基准元素，默认首元素为基准，base=a[p].
2. 开始划分，把比基准base小的元素放在基准的左边，把比基准base大的元素放在基准的右边。
3. 返回基准元素的下标j，也就是说，基准元素在原数组中的排位是j+1。
4. 把k跟j+1比较，如果k==j+1，那么第k小元素就找到了，即为基准base.
5. 如果kj+1,那么说明要求的元素在数组的右边，返回第1步骤，划分a[j+1,r].
6. 直到找到第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 && ix && 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 && ix && 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)，也就是题目的题意所在！！！

四、线性时间选择算法

基本思路：

1.  数组a[p:r],设置一个阈值，问题规模为n(即为数组的元素个数），当n<5时，问题规模很小，可以直接使用冒泡排序求解问题，否则转到步骤2.（其实，n<5设置还不是最优的，正常设置n<75，当考虑到本问题规模为15，比较小，为了应用上本算法，故设置为n<5）。
2. 把原数组划分为n/5组，一般除了最后一组元素不足5个外，其他都满足5个。
3. 把每组元素进行冒泡排序，找出中位数，那么一共有n/5个中位数。
4. 把n/5个中位数提取出来，再进行冒泡排序，得到“中位数中的中位数”x，作为基准。
5. 利用partition划分算法，返回基准x的下标j，并对应计算出x在原数组中的排位i。
6. 把k与i比较，如果k<=i,那么我们要求的第k小元素肯定在a[p:j]中，否则在a[j+1:r]中.
7. 返回步骤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);    } 

 运行结果：

完整的线性时间选择算法代码，想要的朋友可以关注一下小玥发布的资源哦，没找到的可以私聊小玥！！！附赠随机化划分算法randompartition ！！！

创作不易，请多多指教！！！