从一个序列中获取前K大的数的一种方法

这个方法是利用快速排序的。在快速排序中，得到中间元素（pivot）之后，比较中间元素之前的元素个数和K的大小关系，从而确定后面该往哪个方向继续递归。如果中间元素前面的元素个数等于K，那就停止递归过程；如果中间元素前面元素个数小于K，那就再中间元素后面进行递归；否则就往中间元素前面进行递归。这样最终得到的是没有排序的前K大的元素，这样再对前K个元素进行一次真正的快速排序。这样就能得到排好序的前K大元素。我随机生成了一个100000个整型数据的文件进行测试，求前10000个元素。这样做用了0.984s，然后如果直接用快速排序对整个序列进行快速排序，再取前10000个的话，用了1.05。这在某种程度上优化了这个问题。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          using namespace std; template
         
           class Quicksort { inline int static partition(elem a[],int l,int r,elem& pivot) { do { while(a[++l]
          
           =j) return; int pivotindex=(i+j)/2;//get the pivot swap(a[pivotindex],a[j]);//swap the pivot with the last one of the array int k=partition(a,i-1,j,a[j]);//get the correct index of the pivot after partition swap(a[k],a[j]); sort(a,i,k-1);//recursion sort(a,k+1,j);//recursion } static void TopN(elem a[],int i,int j,int n)//get the top N from a[i],...,a[j] ? { ? ?if(i>=j) return ; ?? int pivotindex=(i+j)/2; ?? swap(a[pivotindex],a[j]); ?? int k=partition(a,i-1,j,a[j]); ?? swap(a[k],a[j]); ?? int tem=k-i; ? ?if(tem==n||tem==n-1) return ; ?? else if(tem
           
            n) TopN(a,i,k-1,n); ? } }; int a[100005]; int main() { ? clock_t start=clock(); ? freopen("rand.txt","r",stdin); ? for(int i=0;i<100000;i++) scanf("%d",&a[i]); ? Quicksort
            
             ::TopN(a,0,99999,10000); ? Quicksort
             
              ::sort(a,0,9999); ? for(int i=0;i<9999;i++) printf("%d ",a[i]); ? printf("\n"); ? cout<<"time used:"<<(double)(clock()-start)/CLOCKS_PER_SEC<<"s"<
              
               
 
               





 
               
 
               
 ?? ??