快速选择——模板题

原题链接:

快速选择排序模板题

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 )

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

image-20210203143227647