算法系统学习-找第k小值（非等分分治）
前言
???????????? 该系列是基于有一定语言基础（C，C++，Java等等）和基本的数据结构基础进行的算法学习专栏，如果觉得有点吃力 ???? ，建议先了解前提知识再学习喔！本个专栏会将用更容易理解的表达去学习算法，如果在一些表述上存在问题还请各位多多指点 ???????????? ，要是觉得还不错记得点个 ????本专栏快捷门：juejin.cn/column/7024…
非等分二分法
现实中常见的应用就是寻找中值元素（中值是一个很有用的统计量，例如中间工资，中间年龄，中间重量等），因此经常会遇到在“一组数据中取第k小的值”。
按照以前的最好的排序算法的复杂性是O（nlogn），但我们可以利用二分法将复杂度降为O（n），可这个二分法不是简单典型的二分法分解成完全独立，相似的两个问题，因为在选出分解后第一组的第k小的数据和第二组的第k小的数据，不能保证这两个数据之一是原问题的解。
Case1：
求一组数的第二小的数
算法分析：
在用二等分法分解的两个子集中，无论只选取第二小数据或只选取最小的数据，合并处理后都有可能得不到原问题的解。但若在两个子集中都选取最小的两个值，那原问题中第二小的数据则一定在这四个数据中。由此，将问题转化成“求一组数中较小的两个数”后，二等分法分解就可将原问题“分解为原问题独立且相似的两个问题”。
这样，回溯合并的过程就是从两个子问题选出的共4个数中，选取出较小的两个数，直到回溯结束，就得到一组数中较小的两个数，从而得到了原问题的解。
算法设计：
float a[100]; main(){ int n; float min2; cin>>n; for(i=0;i<n-1;i++){ cin>>a[i]; } min2=second(n); cout<<min2; } second(int n){ float min2,min1; two(0,n-1,min2,min1); return min2; } two(int i,int j, float &fmin2,float &fmin1){ float lmin2,lmin1,rmin2,rmin1; int mid; if(i=j){ fmin2=fmin1=a[i]; }else if(i=j-1){ if(a[i]<a[j]){ fmin2=a[j]; fmin1=a[i]; }else{ fmin2=a[i]; fmin1=a[j]; } }else{ mid=(i+j)/2; two(i,mid,lmin2,lmin1); two(mid+1,j,rmin2,rmin1); if(lmin<rmin1){ if(lmin2<rmin1){ fmin1=lmin; fmin2=lmin2; }else{ fmin1=lmin1; fmin2=rminl; } }else{ if(rmin2<lmin1){ fmin1=rmin1; fmin2=rmin2; }else{ fmin1=rmin1; fmin2=lmin1; } } } } 复制代码小结：
以上算法利用“分解为与原问题相似的两个子问题”的技巧，解决了一个个简单的排序问题。但对于选取第k小元素的问题，则从效率上是无法行得通的。难道就不能使用二分法解决这类问题？分治法中当然不仅仅包括二分法，也可以使用“非等份分解方法”的例子
Case2：
对于给定的n个元素的数组a【0：n-1】，要求从中找出第k小的元素，要求找到第k小的元素
问题分析：
选择问题的一个应用就是寻找中值元素，此时k=【n/2】。我们可以首先选取第一个数作为分界数据，将比它小的数据存在它的左边，将比它大的数据存储在右边，它存储在左右两个子集之间。（类似荷兰国旗问题）这样左右子集就是原问题分解后的独立子问题，再用同样的方法，解决这些子问题。知道每个子集只有一个数据，自然就有序了，也就完成了全部数据的排序工作。
可以通过改写快排算法，一趟排序分解出的左子集中元素个数left，可能有一下三种情况：
nleft=k-1 ，则分界数据就是选择问题的答案
nleft>k-1，则选择问题的答案继续在左子集中找，问题规模变小了
nleft<k-1，则选择问题的答案继续在右子集中找，问题变成选择第k-nleft-1小的数，问题的规模也变小了
算法设计：
xzwt(int a[],int n,int k) //返回a【0：n-1】中第k小的元素 { if(k< 1|| k>n){ error(); } return select(a,0,n-1,k); } select (int a[],int left,int right,int k){ //在a【left:right】中选择第k小的元素 if(left >=right){ return a[left]; } int i=left;//从左至右的指针 j=right+1;//从右至左的指针 int pivot =a[left]; while(1){ do{ //在左侧寻找>=pivot的元素 i=i+1; }while(a[i]<pivot); do{ j=j-1; }while(a[j]>pivot);//在右侧寻找<=pivot的元素 if(i>=j){ break;//未发现交换对象 } Swap(a[i],a[j]); } if(j-left+1=k){ return pivot; } a[left]=a[j];//设置pivot a[j]=pivot; if(j-left+1<k){ 。//对一个段进行递归调用 return select(a,j+1,right,k-j-1+left); }else{ return select(a,left,j-1,k); } }
作者：GTW_Zeus
链接：https://juejin.cn/post/7028754736664838151