找第k小|C语言实现-白红宇的个人博客

找第k小|C语言实现

发布日期：2021-05-07 06:45:58 浏览次数：18 分类：精选文章

本文共 1316 字，大约阅读时间需要 4 分钟。

在这里插入图片描述

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include
        
         #include 
         
          using namespace std;int select_kth_smallest(vector
          
            q, size_t k);int choose_mid(vector
           
            & q, int left, int right);int selection(vector
            
              v);void print_vector(vector
             
               v);int main(){ srand(time(NULL)); int x; int k = 1; vector
              
                v; for(int i = 0;i<10;i++) { x = rand()%100; v.push_back(x); } print_vector(v); k = select_kth_smallest(v,4); cout <

v){ for(vector

::iterator it = v.begin(); it != v.end(); it++) cout << *it << " ";} int select_kth_smallest(vector

q, size_t k){ int bot = 0, top = q.size(); while(bot < top){ int left = bot, right = bot, i; int index = choose_mid(q, bot, top); while(right < top){ if(q[right] < index){ int temp = q[left]; q[left] = q[right]; q[right] = temp; left++; } if(q[right] == index) i = right; right++; } q[i] = q[left]; q[left] = index; if(left+1 < k) bot = left + 1; else if(left+1 > k) top = left; else return index; } return -1;} int choose_mid(vector

& q, int left, int right){ vector

v; while(left+5 < right){ int mid = selection(vector

(&q[left], &q[left+5])); v.push_back(mid); left += 5; } int mid = selection(vector

(&q[left], &q[right])); v.push_back(mid); return selection(v);} int selection(vector

v){ int size = v.size(); for(int a=1; a

0 && temp

上一篇：寻找第k小数

下一篇：送你一颗心Easyx

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章