原题链接：

快速选择排序模板题

AC源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>

using namespace std;

int a[100010];

int quick_sort( int a[], int l , int r, int k)
{
    if ( l == r) return a[l] ;

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

    if(d >= k) return quick_sort(a, l , j , k);
    return quick_sort( a, j + 1 , r, k - d);
}

int main()
{
    int n , k;
    cin >> n >> k;
    for ( int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);

    cout << quick_sort( a , 0 , n - 1, k );

    return 0;
}

快速选择排序原理：

和快速排序的原理差不多

只不过递归的时候，有少许不一样，相比快速排序多一个d参数

d：代表前d项已经被分为了一组，如果此时的d大于k，那么递归quick_sort(q, l , j , k);

否则递归quick_sort( q, j + 1 , r , k - d )

上方a和q数组其实是一样的，只不过是两道题，一道题用的是a，一道题用的是q

image-20210203143227647