题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第k小数。

数据范围

$1≤n≤100000$

$1≤k≤n$

输入样例：

5 3
2 4 1 5 3

输出样例：

3

思路：快速选择算法

快速排序：

1.找到分界点x，q[l],q[l+r>>1],q[r]

2.划分，将整个区间划分为两段，使左边所有的数Left≤x，右边所有的数Right≥x

注意：虽然x是分界点，但最后分成两段的分界点不一定等于x

3.递归排序Left、Right

快速选择：

主要就是在快排的基础上选择一边进行排序，不用两边都排

设Left有SL个元素，Right有SR个元素,k是在整个区间里第k个小的数

有两种情况：

①k≤SL

此时的k一定在左半边，因此只要递归处理Left即可

②k>SL（注意是‘>’）

此时的k一定在右半边，因此只要递归处理Right即可

因为k是在整个区间里第k小的数，因此在递归右半边的时候，k在右半边是第k-SL小的数

快速选择算法 时间复杂度分析：

第一次是对整个区间进行排序，所以时间复杂度是$O(n)$

第二次选择了一边，所以时间复杂度是$O(n/2)$

每一次都选一边，因此每次都÷2，直到只剩一个数（或没有）递归结束

所以时间复杂度应该是$O(n+n/2+n/4+n/8+……)$=>$O(n(1+1/2+1/4+1/8+……)$

因为1+1/2+1/4+1/8+……≤2

所以时间复杂度≤$O(2n)$

常数省略，所以是$O(n)$

写法一快速选择算法(用个数)$O(n)$

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,k;
int q[100010];
int quick_sort(int l,int r,int k)
{
    if(l>=r)
        return q[l];
    int x=q[l+r>>1],i=l-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;
    if(k<=sl) return quick_sort(l,j,k);
    else return quick_sort(j+1,r,k-sl);
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    cout<<quick_sort(0,n-1,k);
    return 0;
}

写法二 快速选择算法(用下标)$O(n)$

这种写法函数的第三个参数没加是因为，这个参数从始至终都没有变化，如果加的话，就直接写k就行了

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, k;
int q[N];
int quick_select(int l,int r)
{
    if (l==r) return q[l];
    int i=l-1,j=r+1,x=q[l+r>>1];
    while (i<j)
    {
        do i ++ ; while(q[i]<x);
        do j -- ; while(q[j]>x);
        if (i<j) swap(q[i],q[j]);
    }
    if (k<=j) return quick_select(l,j);
    else 
        return quick_select(j+1,r);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    k--;//因为是用的坐标，数组从0开始存的，而k是从1开始数的，所以要--
    cout<<quick_select(0,n-1)<<endl;
    return 0;
}

以上两种写法的区别：

这两种写法的区别主要在于函数里的第3个参数

1.含义不同

写法一函数里的第3个参数代表的是，要找的这个数在目前的数组里在第几个位置

写法二函数里的第3个参数代表的是，要找的这个数在a[]里在第几个位置（因为这种写法用的是下标，所以是在a[]里的位置）

写法三 快速排序$O(nlogn)$

#include<iostream>
using namespace std;
int q[100010];
void qsort(int q[],int l,int r)
{
    if(l>=r) return ;
    int x=q[(l+r)/2];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    qsort(q,l,j);
    qsort(q,j+1,r);
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i];
    }
    qsort(q,1,n);
    cout<<q[m];
    return 0;
}

写法四(直接用sort也可以过)$O(nlogn)$

直接排序然后输出第k位

#include<iostream>
#include<algorithm>
using namespace std;
int a[100010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    cout<<a[m];
    return 0;
}

附：快速排序算法模板 AcWing 785. 快速排序

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}