题目：求一个无序数组的中位数。
如：{2,5,4,9,3,6,8,7,1}的中位数为5，{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。
要求：不能使用排序，时间复杂度尽可能高提示：考虑堆或者快排思想解决。采用堆 将前（size+1）/2个元素创建一个小堆 遍历后序的元素大于小堆堆顶的元素则取代堆顶，否则丢弃 堆顶的元素便是中位数 void FindMidNum1(int *arr, int size) { if (NULL == arr || size <= 1) return; priority_queue<int,vector<int>,greater<int>> _pq; for (int i = 0; i <= (size+1)/2; i++) { _pq.push(arr[i]); } for (int j = (size + 1) / 2 + 1; j < size; j++) { int top = _pq.top(); if (arr[j] > top) { _pq.pop(); _pq.push(arr[j]); } } if (size & 1)//奇数个元素 cout << "中位数： " << _pq.top() << endl; else { int tmp = _pq.top(); _pq.pop(); cout << "中位数： " << tmp << " " << _pq.top() << endl; } }1.将数组元素平均分配到大小堆中，保证小堆的元素都比大堆的元素大，那么中位数一定在某堆的堆顶 a.将下标为奇数的元素放到小堆 b.将下标为偶数的元素放到大堆 c.交换堆顶元素保证小堆的元素都比大堆的大
template <typename T> struct greater { bool operator()(int left,int right) { return left > right; } }; void FindMidthNum(int *array,int size) { if (NULL == array || size <= 0) { cout << "args error" << endl; return; } priority_queue<int, vector<int>,greater<int> >min_pq; priority_queue<int>max_pq; for (int i = 0; i < size; i++) { if ((i & 1) == 1)//奇数 min_pq.push(array[i]); else max_pq.push(array[i]); if (!min_pq.empty() && !max_pq.empty()) { int temp = min_pq.top(); min_pq.pop(); max_pq.push(temp); temp = max_pq.top(); max_pq.pop(); min_pq.push(temp); } } if (size & 1) cout << max_pq.top() << endl; else cout << max_pq.top() << " " << min_pq.top() << endl; }采用快排思想 快排思想： 任意选取一个元素将需要排序的集合划分为2个部分，比元素小的在左部分，比元素大的在右部分 如果选取的元素刚好是中位数那么左右部分的元素个数刚好是（size-1）/2 如果小于（size-1）/2那么中位数在右侧，大于（size-1）/2中位数在左半部分
int partion(int *arr, int left, int right, int length) { if (NULL == arr || left < 0 || length < 0 || right >= length) return -1; int pCur = left; int pPre = left - 1; int temp = arr[right]; while (pCur < right) { if (arr[pCur] < temp && ++pPre != pCur) swap(arr[pCur], arr[pPre]); pCur++; } if (++pPre != right) swap(arr[pPre], arr[right]); return pPre; } void GetMidthNum(int *arr,int size) { if (NULL == arr || size <= 1) return; int mid = (size - 1) / 2; int div = partion(arr, 0, size - 1, size); while (div != mid) { if (div > mid)//左部分的元素多，中位数在左侧 { div = partion(arr, 0, div - 1, size); } else if (div < mid)//右部分的元素多，中位数在右侧 { div = partion(arr, div + 1, size - 1, size); } else //找到中位数 break; } cout << "中位数 ： " << arr[div] << endl; }