O(n)算法得到数组中任意第k大的数字

秒速五厘米 2022-05-20 04:52 159阅读 0赞

利用快速排序的思想，任意取某个数p，然后小于p的放左边，大于p的放右边。一次快排后p最后所在的位置是最终位置，然后看位于k的左边还是右边再递归。

缺点：会改变原来的数组

#include <iostream>
    #include <time.h>
    
    using namespace std;
    
    
    int Partition(int a[],int left,int right)
    {       
            if(left<right)
            {       
                    int i=left,j=right;
                    int x=a[left];
                    while(i!=j)
                    {       
                            while(i<j && a[j]>x)
                                    j--; 
                            while(i<j && a[i]<=x)
                                    i++;
                            if(i<j) 
                                    swap(a[i],a[j]);
                    
                    }
                    a[left]=a[i];
                    a[i]=x;
                    return i;
            }
    }
    
    int Find(int a[],int n,int k)
    {
    
            int left=0;
            int right=n-1;
            int index=Partition(a,left,right);
            while(index!=k)
            {
                    if(index>k)
                    {
                            right=index-1;
                            index=Partition(a,left,right);
                    }
                    else
                    {
                            left=index+1;
                            index=Partition(a,left,right);
                    }
    
            }
            return a[k];
    }
    int main(void)
    {
            srand((unsigned)time(0));
            const int n=20;
            int a[n];
            for(int i=0;i<n;i++)
                    a[i]=rand()%200;
            for(int i=0;i<n;i++)
                    cout<<a[i]<<' ';
    
            cout<<endl<<"-------------------"<<endl;
            cout<<"请输入一个数字K，按回车结束"<<endl;
            int k;
            cin>>k;
            cout<<Find(a,n,k);
    
            cout<<endl<<"-------------------"<<endl;
            for(int i=0;i<n;i++)
                    cout<<a[i]<<endl;
    
            return 0;
    }