以下程序用在n个不同元素中找出第k个最小元素。程序中用分治策略来设计算法。把这n个元素放在一个数组中，然后取出第k个元素为标准X，把n个元素重新排列：小于标准X的元素放在数组前面，大于该标准X的放在数组的后面。把该元素X放在两者之间。设小于标准的元素个数为i-1，如果i==k，则A[k]即为所求元素。如果i>k，则第k个元素必在区间[1, i-1]，因此取A[1],…,A[i-1]为新的元素集合，然后重复上述的“部分排序”的过程。如果i<k，则第k个元素必在区间[i+1,n]，因此取A[i+1],…, A[n]为新的元素集合，重复过程。直至i == k为止。
#include<iostream>
using namespace std;
int a[110];
int n, k;
void search(int ll, int rr)
{
if(ll == rr) return;
int i = ll, j = rr, X = _____(1)______;
do
{
while(a[i] < X) i++;
while(X < a[j]) ____(2)______;
if(i < j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}while(i < j);
if(i == k) return;
if(i > k) search(ll, i-1);
else _____(3)_______;
}
void pr(int n)
{
for(int i = 1; i <= n; i++) cout << a[i] << ' ';
cout << endl;
cout <<"a["<< k <<"]=" << _____(4)_____<< endl;
}
int main( )
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin>>k;
search(____(5)_____);
pr(n);
return 0;
}