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

#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 << k << endl; sort(v.begin(), v.end()); print_vector(v); return 0; } void print_vector(vector
               
                 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(q, left, right - left + 1); v.push_back(mid); left += 5; } mid = selection(q, left, right); v.push_back(mid); return selection(v); } int selection(vector
                    
                      v) { int size = v.size(); for(int a = 1; a < size; a++) { int b = a; int temp = v[b]; while(b < 0 && temp > v[0]) { b--; temp = v[b]; } return temp; } }