基于快排的选择算法:就是从数组中随机选一个数，比这个数小的放左边，大的放右边，如果放左边的数的个数等于k-1，说明现在选的这个数就是第k大的数。如果放左边的数的个数大于k个，则递归寻找左边的数组中的第k小的元素，找出的这个数，就是原来数组中的第k大元素。 如果放左边的数的个数小于k个，则在右边的数组当中找第k-p-1小的元素（p为左边数组的大小）。

  基于堆的选择算法：维护一个k个元素的最大堆，首先从数组当中取出k个数填入这个堆。然后每次从数组中取出一个元素，和堆顶进行比较。如果比堆顶元素大，则忽略。如果比堆顶元素小，则替换掉堆顶元素，并做一次下滤。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include "windows.h"using namespace std;bool cmp(int a,int b){ return a
           
            = end-1) return testData1[start]; int x = start; int tmp = rand()%(end-start)+start; swap(testData1[x],testData1[tmp]); tmp = testData1[x]; int y = end-1; while(x < y){ while (x < y && testData1[y] >= tmp){ y--; } if (x < y){ testData1[x] = testData1[y]; x++; } while (x < y && testData1[x] <= tmp){ x++; } if (x < y){ testData1[y] = testData1[x]; y--; } } testData1[x] = tmp; if (x-start == order-1) return testData1[x]; if (x-start >= order){ return search1(start, x , order); } else{ return search1(x+1 , end , order-(x-start)-1 ); }}//堆方法int search2(int start, int end , int order){ make_heap(&testData2[0],&testData2[order],cmp); for (int i = order ; i < num; i++){ if (testData2[i] < testData2[0]){ pop_heap(&testData2[0],&testData2[order],cmp); testData2[order-1] = testData2[i]; push_heap(&testData2[0],&testData2[order],cmp); } } return testData2[0];}int main(){ srand(time(0)); cout << "k time1 time2"<
           
          
         
        
       
      
     

 

实验结果：

 

PS：基于快排的算法不稳定，最坏情况是O(n^2)的。在算法导论第9.3节有一个最坏情况为O(n)的选择算法。 

版权声明：本文为博主原创文章，未经博主允许不得转载。