选第k小元素，特定分治策略

1. 问题
   [描述算法问题，首选形式化方式（数学语言），其次才是非形式化方式（日常语言）]
   设L是n个元素的集合，从L中选取第k小的元素，其中1<=k<=n.这里的第k小元素是指，当L按从小到大排好序之后，排在第k个位置的元素。

2. 解析
   [问题的理解和推导，可用电子版直接在此编写，也可用纸笔推导，拍照嵌入本文档]
   

3. 设计
   [核心伪代码]
   int select(int a[],int l,int r,int k) {
   int group,i,left,right,mid,pivot,p,left_num;
   if(r-l+1<=5) {
   insertsort(a,l,r);
   return a[l+k-1];
   }

   group=(r-l+1+5)/5;
   for(i=0; i<group; i++) {
   left=l+5i;
   right = (l+5i+4)>r?r:l+5*i+4;
   mid=(left+right)/2;
   insertsort(a,left,right);
   swap(a,l+i,mid);
   }
   pivot=select(a,l,l+group-1,(group+1)/2);
   p = partition(a,l,r,pivot);
   left_num = p-1;
   if(k==left_num+1)
   return a[p];
   else if(k<=left_num)
   return select(a,l,p-1,k);
   else
   return select(a,p+1,r,k-left_num-1);
   }

4. 分析
   [算法复杂度推导]
   O（n）

5. 源码
   [github源码地址]
   https://github.com/zddhandsome/Algorithm/blob/main/%E9%80%89%E7%AC%ACk%E5%B0%8F%E5%85%83%E7%B4%A0%EF%BC%9A%E7%89%B9%E5%AE%9A%E5%88%86%E6%B2%BB%E7%AD%96%E7%95%A5.cpp

最后

以上就是飘逸身影为你收集整理的选第k小元素，特定分治策略的全部内容，希望文章能够帮你解决选第k小元素，特定分治策略所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。