第k小数

解题思路
采用快排的思想，每次确定第k小数所在的区间，直到区间只剩下一个元素，或者k处在mid位置

AC代码

#include <iostream>

using namespace std;
const int N=5000010;
int a[N];

int finding(int l,int r,int k)
{
    if(l==r) return a[l];
    int i=l,j=r;
    int mid=(l+r)>>1;
    int x=a[mid];
    while(i<=j)
    {
        while(a[j]>x) j--;
        while(a[i]<x) i++;
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++,j--;
        }
    }
    if(k<=j) return finding(l,j,k);
    else if(k>=i) return finding(i,r,k);
    else return a[k];
}

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    int t;
    t=read();
    int n,k;
    while(t--)
    {
        n=read(),k=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        printf("%d\n",finding(1,n,k));
    }

    return 0;
}

注意
a[mid]的值要用一个变量x代替，在交换的过程中，mid位置上的元素会发生改变

还可以使用STL库函数nth_element()求第k小数

#include <bits/stdc++.h>

using namespace std;
const int N=5000010;
int a[N];

static char buf[100000], * pa = buf, * pb = buf;
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
inline long long int read()
{
    long long int x(0); char c(gc);
    while (c < '0' || c>'9')c = gc;
    while (c >= '0' && c <= '9')x = (x << 1) + (x << 3) + (c ^ 48), c = gc;
    return x;
}


int main()
{
    int t;
    t=read();
    int n,k;
    while(t--)
    {
        n=read(),k=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        nth_element(a+1,a+k,a+n+1);
        printf("%d\n",a[k]);
    }

    return 0;
}