快排-前m大元素

描述 给定一个数组包含n个元素，统计前m大的数并且把这m个数从大到小输 出。 
 

输入 第一行包含一个整数n，表示数组的大小。n < 100000。

第二行包含n个整数，表示数组的元素，整数之间以一个空格分开 。每个整数的绝对值不超过100000000。

第三行包含一个整数m。m < n。

输出 从大到小输出前m大的数，每个数一行。 

排序后再输出，复杂度 O(nlogn) 
 
用分治（快排）处理：复杂度 O(n+mlogm)

思路：把前m大的都弄到数组最右边，然后对这最右边m个元素排序， 再输出 
 
关键 ：O(n)时间内实现把前m大的都弄到数组最右边 

 如何将前k大的都弄到最右边

1）设key=a[0], 将key挪到适当位置，使得比key小的元素都在 key左边，比key大的元素都在key右边（线性时间完成） 

2) 选择数组的前部或后部再进行 arrangeRight操作       
a = k        done  

a > k        对此a个元素再进行arrangeRigth(k)

a < k     对左边b个元素再进行arrangeRight(k-a) 

时间复杂度：

将前m大的都弄到数组最右边的时间： 
 
T(n) = T(n/2) + a*n      

= T(n/4) + a*n/2 + a*n      

= T(n/8) + a*n/4 + a*n/2 + a*n      

= ...      

= T(1) + ... + a*n/8 + a*n/4 + a*n/2 + a*n  <  2*a*n  
 
 即 O(n) 
 

代码实现

很简单，看主要代码

  

   

    

     

    
    

     

      int a[N];
     
    
   

    

     

    
    

     

      int swap(int &a,int &b){
     
    
   

    

     

    
    

     
 int tmp=a;
     
    
   

    

     

    
    

     

       a=b;
     
    
   

    

     

    
    

     

       b=tmp;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      void arrangeRight(int *a,int s,int e,int k){
     
    
   

    

     

    
    

     
 if(s>=e)
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     
 int t=a[s];
     
    
   

    

     

    
    

     
 int i=s,j=e;
     
    
   

    

     

    
    

     
 while(i!=j)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 while(i<j&&t<=a[j])--j;
     
    
   

    

     

    
    

     

       swap(a[i],a[j]);
     
    
   

    

     

    
    

     
 while(j>i&&t>=a[i])++i;
     
    
   

    

     

    
    

     

       swap(a[i],a[j]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int num=e-i+1;
     
    
   

    

     

    
    

     
 if(num==k) return;
     
    
   

    

     

    
    

     
 else if(num>k) arrangeRight(a,i+1,e,k);
     
    
   

    

     

    
    

     
 else if(num<k) arrangeRight(a,s,i-1,k-num);
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/81772978