对于曾经，假设要我求第k小元素。或者是求前k大元素，我可能会将元素先排序，然后就直接求出来了，可是如今有了更好的思路。

一.线性时间内求第k小元素

这个算法又是一个基于分治思想的算法。

其详细的分治思路例如以下：

1.分解：将A[p,r]分解成A[p,q-1]和A[q+1,r]两部分。使得A[p,q-1]都小于A[q],A[q+1,r]都不小于A[q];

2.求解：假设A[q]恰好是第k小元素直接返回，假设第k小元素落在前半区间就到A[p,q-1]递归查找。否则到A[q+1,r]中递归查找。

3.合并：这个问题不须要合并。

其相应的代码例如以下：

int RandomziedSelect(int *a,int p,int r,int k){    if(p==r)///假设当前区间仅仅剩一个元素,那么这个元素一定就是我们要求的        return a[p];    int q=RandomParatition(a,p,r);  ///随机划分函数    int x=q-p+1;///求出a[p,q]之间的长度    if(x==k) ///a[q]恰好是第k小元素        return a[q];    if(x>k)  ///x小于k说明第k小元素在a[p,q-1]之间        return RandomziedSelect(a,p,q-1,k);    else  ///x大于k说明第k小元素在a[q+1,r]之间,并且是这个区间的第k-x小元素        return RandomziedSelect(a,q+1,r,k-x);}

事实上这个过程非常相似于快排，可是为什么快排的时间复杂度是O(nlgn)，而这个算法的时间复杂度仅仅有O(n)?基本的原因在于这个算法每次仅仅要处理分解以后一半的区间，而不像快排那样两边都要处理。

当然这仅仅是一个简单的分析，更详细数学分析在这里就不说了。事实上我们也能够利用堆的性质来求出第k小元素，仅仅要我们建立一个最小堆后然后再调整k-1次即可了，这样时间复杂度是O(n)+O((k-1)lgn)。

以下给出一份完整的代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int Paratition(int *a,int p,int r){ int key=a[r]; int i=p-1; for(int j=p;j
             
              k) ///x小于k说明第k小元素在a[p,q-1]之间 return RandomziedSelect(a,p,q-1,k); else ///x大于k说明第k小元素在a[q+1,r]之间,并且是这个区间的第k-x小元素 return RandomziedSelect(a,q+1,r,k-x);}int main(){ int b[100]; ifstream fin("lkl.txt"); int n,k; //cout<<"请输入n,k: "; fin>>n>>k; //cout<<"请输入"<
              
               <<"个元素: "<
               
                >b[i]; int ans=RandomziedSelect(b,1,n,k); sort(b+1,b+n+1); for(int i=1;i<=n;i++) cout<
                
                 <<" "; cout<
                
               
              
             
            
           
          
         
        
       
      

二.利用堆求前k大元素

这个算法的思想比較简单: 假设我们要求n个元素中前k大的元素。我们就先将这n个元素中的前k个元素建立一个最小堆,然后从k+1。

。。

n依次推断。假设某个元素大于堆中最小的元素，我们就将其替代堆中的最小元素，并且调整一下堆。

这样将全部元素都检查完了之后，堆中的k个元素也就是这n个元素中的前k大元素了。时间复杂度O(k)+O((n-k)lgk)。

代码例如以下

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define maxn 100///最小堆调整函数void MinHeadfly(int *a,int i,int HeadSize){    int l=i*2,r=2*i+1;    int largest;    if(a[i]>a[l]&&l<=HeadSize)        largest=l;    else        largest=i;    if(a[largest]>a[r]&&r<=HeadSize)        largest=r;    if(largest!=i)    {        swap(a[i],a[largest]);        MinHeadfly(a,largest,HeadSize);    }}///最小堆建立函数void MinHeadBuild(int *a,int n){    for(int i=n/2;i>=1;i--)        MinHeadfly(a,i,n);}///最小堆排序函数,从大到小排序void MinHeadSort(int *a,int HeadSize){    int k=HeadSize;    for(int i=HeadSize;i>=2;i--)    {        swap(a[i],a[1]);        k--;        MinHeadfly(a,1,k);    }}///求b数组的前k大元素void prek(int *a,int *b,int n,int k){    MinHeadBuild(a,k);    for(int i=k+1;i<=n;i++)        if(b[i]>a[1])        {            a[1]=b[i];            MinHeadfly(a,1,k);        }    MinHeadSort(a,k);    cout<<"前"<
           
            <<"大元素为："<
            
             >n>>k; //cout<<"请输入"<
             
              <<"个元素: "<
              
               >b[i]; if(i<=k) a[i]=b[i]; } prek(a,b,n,k); return 0;}