六.快速选择算法（在一个数组里查找第k小的数字

在一个数组里实现快速选择。首先执行快速排序的前两步，得到以分界点为界的左右两个区间，然后比较左区间中数的个数与k的大小，如果小，说明第k小的数在左区间里面，反之则在右区间里面，此时只要对左区间或者右区间进行递归快速排序即可。

 

#include<iostream>using namespace std;const int N=100010;int n,k;
ing q[N];intquick_sort(int l,int r,int k){if(l==r) return q[l];//当l=r的时候说明区间里只有一个数，则这个数一定是结果int x=q[l],i=i-1,j=r+1;while(i<j){while(q[++i]<x);while(q[--j]>x);if(i<j) swap(q[i],q[j]);}int sl=j-l+1;//因为移动到最后，右边界是j，左边界是l。sl是左区间长度if(k<sl) return quick_sort(l,j,k);return quick_sort(j+1,l,k-sl);
}int main(){cin>>n>>k;for(int i=0;i<n;i++)cin>>q[i];cout<<quick_sort(0,n-1,k)<<endl;return 0;
}