排序后第k位置数.cpp

来自「一些比较难找的算法代码 中国剩余定理.cpp 高斯消元.cpp 红黑树.c」· C++ 代码 · 共 21 行

double select(int low,int high,int k)
{
        if(low==high) return a[low];
        int r = low+rand()%(high-low+1);
        double t=a[r];a[r]=a[low];a[low]=t;
        int t1,t2;
        t1=low;t2=high;
        while(t1<t2){
                while(!(a[t2]+eps<t)&&t2>t1) t2--;
                a[t1]=a[t2];
                while(!(a[t1]>t+eps)&&t1<t2) t1++;
                a[t2]=a[t1];
        }
        a[t1]=t;
        if(t1==k) return a[t1];
        if(t1<k) return select(t1+1,high,k);
        if(t1>k) return select(low,t1-1,k);
        
}