Ⅰ.快速选择算法介绍：
快速选择算法思路几乎与快速排序算法相同。快速选择算法可以快速求出序列中第k小的元素。
Ⅱ.快速选择算法的思路：
快速选择算法可以看作是快速排序算法的“一半”。快速排序算法可以得出整个序列的大小顺序，但是，现在我只想知道第k小的元素是什么，其余的不关心。求第k小的元素而把整个序列排序又太过小题大作。
那么，现在进行的是快速排序算法，假设我选取的枢纽元是p。
在双指针交换元素之后，[ l, j ]区间是全部小于p的元素， [ j + 1, r ]区间是全部大于p的元素。
若此时 k 小于等于 j指针 ，说明答案只会在 [ l, j ] 之间。若此时k 大于 j指针，说明答案只会在[ j + 1, r]之间。则另外的区间就不必进行递归处理了，因为答案肯定不在里面，处理了也是做的无意义的花费。
Ⅲ.代码实现：
#include<iostream> #include<algorithm> using namespace std; const int N = 100010; int q[N]; int n, k; void quickselect( int a[], int k, int l, int r ) { if( l >= r ) return; int pivot = a[(l+r>>1)]; int i = l - 1, j = r + 1; while ( i < j ){ while( a[++i] < pivot ); while( a[--j] > pivot ); if( i > j ) break; else swap( a[i], a[j] ); } if( k <= j ) quickselect( a, k, l, j ); else quickselect( a, k, j + 1, r ); } int main() { cin >> n >> k; for( int i = 0; i < n; i++ ) cin >> q[i]; quickselect( q, k - 1, 0, n - 1 );//第k个数在序列中的下标是 k-1 cout << q[k-1] << endl; return 0; }
Ⅳ.注意：
快速选择会破坏原序列元素的顺序，如果只想找出最小的第k个数而不想破坏顺序，则应该对序列的拷贝进行操作。
