在做uva11300时，遇到了n < 1000 000的中位数，就看了一下线性求中位数。
该算法的最差时间复杂度为O(N^2)，期望时间复杂度为O(N)，证明推理详见算法导论P110。
和快排的思想很像，同理，线性求第k大数，算法如下：
①以某个数x将一段数组分成两部分，比x小的放在左边，比x大的放在右边
②如果x刚好是出于要找的位置的，直接返回
③如果在x的左边，则递归在x的右边找
④如果在x的右边，则递归在x的左边找
代码如下：
/*===============================================================
* Copyright (C) 2014 All rights reserved.
*
* File Name: poj2388.cpp
* Author:sunshine
* Created Time: 2014年07月28日
*
================================================================*/
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm> using namespace std; int find_mid(int arr[], int left, int right, int x){
if(left >= right){
return arr[left + x];
}
int mid = arr[left];
int i = left;
int j = right;
while(i < j){
while(i < j && arr[j] >= mid) j--;
arr[i] = arr[j];
while(i < j && arr[i] <= mid) i++;
arr[j] = arr[i];
}
arr[j] = mid;
if(i - left == x) return arr[i];
if(i - left < x) return find_mid(arr, i + , right, x - (i - left + ));
else return find_mid(arr, left, i - , x);
} int arr[];
int main(){
int n;
while(scanf("%d", &n) != EOF){
for(int i = ;i < n;i ++){
scanf("%d", &arr[i]);
}
printf("%d\n", find_mid(arr, , n-, n / ));
}
return ;
}