地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4322
题意：寻找中位数。对于一个（浮点数）数组，如果含有奇数个元素，“中位数”就是排序后位于数组中间那个。如果含有偶数个元素，“中位数”是排序后数组中间那两个元素的平均值。
此题应该是直接取自《算法导论》第9章（中位数和顺序统计学）的命题。如果对数组排序，再得出中位数，时间复杂度是 O(n log n) ，但这样的效率不高。对于这个命题不需要排序，算法导论的 9.2 节给出平均情况为 O（n）的方法，代码类似快排，其最差情况是 O（n^2)，但由于对数组随机选取一个点作为分割点，所以最差情况几乎不可能发生。第 9.3 节给出一种最差情况也能达到线性时间的方法，但编码实现比较麻烦。书中也没有给出伪码。以下代码是第 9.2 节中的方法：
#include <stdio.h> #include <stdlib.h> double nums[500]; void exchange(double* A, int i, int j) { double tmp; if(i != j) { tmp = A[i]; A[i] = A[j]; A[j] = tmp; } } /* 以A中最后一个元素作为分割点，把A就地划为为两个子序列 */ int fix_partition(double* A, int begin, int end) { double x = A[end]; int i = begin - 1, j; for(j = begin; j < end; j++) { if(A[j] <= x) { i++; exchange(A, i, j); } } exchange(A, i+1, end); return i + 1; } /* 从A中随即取一个元素作为分割点，把A就地划为为两个子序列 */ int random_partition(double* A, int begin, int end) { int i = rand() % (end - begin + 1) + begin; exchange(A, i, end); return fix_partition(A, begin, end); } /* 返回数组 A[begin, ..., end] 中第 i 小的数字，即排序后的 A[begin + i -1] */ double random_select(double* A, int begin, int end, int i) { if(begin == end) return A[begin]; int q = random_partition(A, begin, end); int k = q - begin + 1; if(i == k) { return A[q]; } else if(i < k) { return random_select(A, begin, q-1, i); } else { return random_select(A, q+1, end, i-k); } } int main(int argc, char* argv[]) { int i, j; int T, n; scanf("%ld", &T); double result; for(i = 0; i < T; i++) { scanf("%ld", &n); for(j = 0; j < n; j++) scanf("%lf", nums + j); if(n & 1) { result = random_select(nums, 0, n-1, n/2+1); } else { result = random_select(nums, 0, n-1, n/2); result += random_select(nums, 0, n-1, n/2+1); result *= 0.5; } printf("%.3lf\n", result); } return 0; }
参考资料：
（1）《算法导论》第9章，中位数和顺序统计学。
