快速选择问题 【快排】

题目：快速选择问题

题意：输入n个整数和一个正整数k（1≤k≤n），输出这些整数从小到大排序后的第k个（例如，k=1就是最小值）。n≤10^7。 

思路：首先想到的是先排序然后输出对应下标即可，但是范围是10^7, 快排的速度是nlogn，如果限制速度的话就超时了！

我们可以在快排的过程中寻找k的范围，快排的是否要划分左右俩部分，这样我们每回划分时看k在左边还是右边，这样我们每次只需递归一半就可以了，只需排序k的范围内的数，其余的没有必要！

参考：紫书-快速排序-P227

代码：

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn = 100;int n,k;int QKPass(int r[],int left,int right){//一次快排，即划分左右部分    int x = r[left];//基数    while(left < right){        while(left < right && r[right] >= x) right--;//从右端开始寻找一个比基数小的数        if(left < right) {r[left] = r[right]; left++;}//将小的数交换到左边        while(left < right && r[left] < x) left++;//从左端寻找比基数大的数        if(left < right) {r[right] = r[left]; right--;}//将大的数交换到右边    }    r[left] = x;//将基数放到中间部分    return left;//返回基数位置}void QKsortK(int r[],int left,int right){    if(left < right){        int pos = QKPass(r,left,right);//基数位置        if(k-1 <= pos - left +1) QKsortK(r,left,pos-1);//当k在左半部分时        else QKsortK(r,pos+1,right);//当k在右半部分时    }}int main(){    int a[maxn];    while(~scanf("%d%d",&n,&k)){        for(int i=0;i<n;i++) scanf("%d",&a[i]);        QKsortK(a,0,n-1);        PRintf("%d/n",a[k-1]);    }    return 0;}