【问题求解】假设无序序列存放在a[0...n-1]中，若将a递增排序，则第k小的元素为a[k-1]。采用类似快速排序的思想。
源代码如下：
#include <iostream> using namespace std; //寻找一个序列中第k小的元素 //运用快速排序和二分查找相结合的方法进行查找 int SearchK(int a[],int low,int high,int k) { //这里是利用快速排序的原理 int i = low, j = high; int tmp; if (low==high&&low==k-1){ //递归出口，区间内只有一个元素且为a[k-1] return a[k - 1]; }else if(low < high){ //区间至少存在两种元素的情况 tmp = a[low]; //选取区间的第一个元素作为基准 while (i!=j) { //从区间的两端交替向中间扫描，直到i=j为止 while (j>i&&a[j]>=tmp) { j--; //从右向左扫描，找第一个关键字小于tmp的a[j] } a[i] = a[j]; //将a[j]前移到a[i]的位置 while (i<j&&a[i]<=tmp) { i++; //从左向右扫描，找第一个关键字大于tmp的a[i] } a[j] = a[i]; //将a[i]后移到a[j]的位置 } a[i] = tmp; //这里是利用二分查找的原理 if (k-1==i) { return a[i]; } else if (k-1<i) { SearchK(a, low, i - 1, k); //在左区间中递归查找 } else { SearchK(a, i+1,high, k); //在右区间中递归查找 } } } int main() { int n = 0; cout << "请输入数组元素的个数：" << endl; cin >> n; int *a = new int[n]; cout << "请输入数组元素" << endl; for (int i = 0; i < n; i++) { cin >> a[i]; } cout << "请输入要查找的第k小的元素的序号" << endl; int k = 0; //输入k cin >> k; int y=SearchK(a, 0, n - 1, k); cout << "第" << k << "小的元素为：" << y << endl; system("pause"); return 0; }输出：
请输入数组元素的个数： 9 请输入数组元素 9 6 3 8 5 2 7 4 1 请输入要查找的第k小的元素的序号 5 第5小的元素为：5 请按任意键继续. . .
