以前写过的一篇，搬过来。
上算法课的时候听到老师讲这个问题，觉得还是蛮有意思的。已知数组A，找出A[m]...A[p]中的第k大值。
很容易想到快排和冒泡。
第一种方法：用快排的分治方法，是先任意找数组中的一个元素a（a用数组的第一个元素比较方便），然后进行一次划分，就是将数组中所有大于a的数都移到a的一边，所有小于等于a的数都移到A的另一边。然后选择在哪边继续进行划分，最后找到第k大的值。
第二种方法：用冒泡的方法，是每个元素挨着比，第一趟找出最大的数，第二趟找出第2大的数，一直到找到第k大的数结束。
其实第一种方法的平均复杂度能到O(n)，但是它的复杂度依赖于划分元素，最坏的时间复杂度是O(n^2)。
如果在第一种方法之上，加上一个筛选划分元素的过程，就能把最坏时间复杂度降到O(n)。筛选的过程就是把所有的数等分成很多小段，然后求所有小段的中间值。构成一个由所有中间值组成的段，然后再取中间值，作为划分元素。即中间值的中间值作为划分元素。取中间值可以先任选一种排序方法排序之后选择，因为每一小段的长度很短，不是影响复杂度的主要因素；取中间值的中间值，利用递归的方法调用自身即可。
这样就可以把最坏时间复杂度降到O(n)了，复杂度证明比较繁琐。
用C++实现了一下：
#include<iostream> using namespace std; int r = 5; //定义全局变量r, r个元素一段 void InSort( int A[], int m, int p ) //插入排序 { int i; for( i = m + 1; i <= p; ++i ) { int t; t = A[i]; int j; for( j = i - 1; j >= m; --j ) { if( t < A[j] ) A[j+1] = A[j]; else break; } A[j+1] = t; } } void Swap( int &a, int &b ) //两数交换 { int temp = 0; temp = a; a = b; b = temp; } int Partition( int A[], int m, int p ) //一次划分函数 { int i = m, j = p + 1; int x = A[m]; while( 1 ) { while( A[++i] > x ); while( A[--j] < x ); if( i >= j) break; Swap( A[i], A[j] ); } A[m] = A[j]; A[j] = x; return j; } int Select( int A[], int m, int p, int k ) //返回一个i值，使得A[i]是A[m..p]中第k小元素 { int n = 0, i = 1, j = 0; if( p - m + 1 <= r ) { InSort( A, m, p ); return m + k - 1; } while( 1 ) { n = p - m + 1; for ( i = 1; i <= int(n/r); ++i ) { //计算中间值 InSort( A, m + (i - 1) * r, m + i * r - 1 ); //将中间值收集到A[m..p]的前部 Swap( A[m+i-1], A[m+(i-1)*r+int(r/2)] ); } j = Select( A, m, m + int(n/r) -1, int(int(n/r)/2) + 1 ); Swap( A[m], A[j] ); //产生划分元素 j = Partition( A, m, p ); if( j - m + 1 == k) return j; else if( j - m + 1 > k ) p = j - 1; else { k = k - ( j - m + 1 ); m = j + 1; } } } int main() { int A[24] = { 1, 3, 6, 33, 4, 1, 5, 2, 9, 8, 50, 22, 2, 23, 22, 45, 7, 18, 20, 40, 36, 22, 23, 10}; int find_out = Select( A, 0, 23, 7 ); int i; for( i = 0; i <= 23; ++i ) cout << A[i] <<" "; cout << endl; cout << A[find_out] << endl; return 0; }
另外：
1、上面说的都是在内存够用的前提下。
2、调这个程序的时候发现了一个问题：
以前我以为下面这样交换两个数比较好。
void Swap( int &a, int &b ) { a = a ^ b; b = a ^ b; a = a ^ b; }
才发现如果a和b表示同一个地址的时候，就是错的（不管是什么都变成0了）。
所以如果可能出现a、b是同一个地址上的数的时候，为了避免有隐藏的bug，还是下面这样保险。（虽然多了一个临时变量的空间）
void Swap( int &a, int &b ) { int temp = 0; temp = a; a = b; b = temp; }