快速选择
原题链接:
AC源代码:
#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