问题描述：
给定一个整数序列，求中位数。如果序列个数为奇数，中位数为升序的中间位置，如果是偶数，这位升序的中间两个数的平均值。
输入：
输入包含多组测试数据，每一组第一行为n(n<104)表示这个序列的个数，接下来有n个整数k(0<k<231-1)
输出：
输出这个序列的中位数
样例输入：
9
1 4 2 5 9 7 8 3 6
样例输出：
5
#include <bits/stdc++.h>using namespace std;#define MAX 10000int a[MAX];void quicksort(int *sta, int *end){int *left = sta, *right = end-1;if(left < right){int key = *left;while(left < right){while(left < right && *right > key) right--;*left = *right;while(left < right && *left < key) left++;*right = *left; }*left = key;quicksort(sta, left);quicksort(left+1, end) ;}}int main(){int n;cin >> n;for(int i=0; i<n; i++) cin >> a[i];quicksort(a, a+n);if(n){if(n%2==1) cout << a[n>>1];else cout << (a[n>>1]+a[(n-1)>>1])/2.0;}return 0;}
