问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。在线性时间内O（n）？
解析：
定义查找第k小元素的算法为 Select(Type a[], int p, int r, int k) 。将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用算法select来找出这n/5个元素的中位数。
如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。
伪代码：
Type Select(Type a[], int p, int r, int k) { if (r-p<75) { 用某个简单排序算法对数组a[p:r]排序; return a[p+k-1]; }; for ( int i = 0; i<=(r-p-4)/5; i++ ) //将元素每5个分成一组，分别排序 BubbleSort(a,p+5*i,p+5*i+4); //将该组中位数与a[p+i]交换位置,即： 将a[p+5*i] 至 a[p+5*i+4]的第3小元素与a[p+i]交换位置; Swap(a[p+5*i+2],a[p+i]); //找中位数的中位数，r-p-4即上面所说的n-5 Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); int i=Partition(a,p,r, x), j=i-p+1; if (k<=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j); }注：来自《计算机算法设计与分析》（第四版）王晓东 编著
代码：
#include <bits/stdc++.h> using namespace std; int Partition(int *a, int p, int n, int beginval) { int temp, beginpos; for(int i = 0; p <= n - p + 1; ++i) if(a[p + i] == beginval) { beginpos = p + i; break; } temp = a[p]; a[p] = a[beginpos]; a[beginpos] = temp; temp = a[p]; while(p < n) { while(a[n] >= temp && p < n) --n; a[p] = a[n]; while(a[p] <= temp && p < n) ++p; a[n] = a[p]; } a[p] = temp; return p; } int Select(int *a, int p, int n, int k) { int temp; if(n - p < 75) { sort(a + p, a + n); return a[p + k - 1]; } else { int ArrNum = (n - p + 1) / 5, i; if(5 * ArrNum != n - p + 1) ++ArrNum; for(i = 0; i < ArrNum - 1; ++i) { sort(a + p + i * 5, a + p + i * 5 + 4); temp = a[p + i]; a[p + i] = a[p + i * 5 + 2]; a[p + i * 5 + 2] = temp; } sort(a + p + i * 5, a + n); int midval = Select(a, p, p + ArrNum, ArrNum / 2); int midpos = Partition(a, p, n, midval); int ranking = midpos - p + 1; if(k <= ranking) return Select(a, p, midpos, k); else return Select(a, midpos + 1, n, k - ranking); } } int main() { int a[100]; int n, k; scanf("%d %d", &n, &k); for(int i = 0; i < n; ++i) scanf("%d", &a[i]); int val = Select(a, 0, n, k); printf("%d\n", val); }