求一个无序数组的中位数，如：{2,5,4,9,3,6,8,7,1}的中位数为5，{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。 要求：不能使用排序，时间复杂度尽可能低。 解决方案一：采用堆排序思想 1、将前(n+1)/2个元素调整为一个小顶堆 2、对后续的每一个元素，和堆顶比较，如果小于等于堆顶，丢弃之，取下一个元素。如果大于堆顶，用该元素取代堆顶，调整堆，取下一元素 3、当遍历完所有元素之后，堆顶即是中位数 建一个小顶堆，需要用到STL里面的 priority_queue，priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数：
priority_queue<Type, Container, Functional>其中Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。 Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list. STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。 如果要用到小顶堆，则一般要把模板的三个参数都带进去。 STL里面定义了一个仿函数 greater<>，对于基本类型可以用这个仿函数声明小顶堆 对于自定义类型，则必须自己重载 operator< 或者自己写仿函数
struct greater{ bool operator() (int a, int b) { return a>b; } }; void GetMidNum(int array[], int size) { priority_queue<int, vector<int>, greater > minHeap; int midSize = (size+1)/2;//将前面一半的数据构造成小顶堆 for (int i = 0; i <= midSize; ++i) minHeap.push(array[i]); //将剩余数据与堆顶比较，如果小于等于堆顶，丢弃之，取下一个元素。如果大于堆顶，用该元素取代堆顶 for (int i = midSize + 1; i < size; ++i) { int temp = minHeap.top(); if (array[i] > temp) { minHeap.pop(); minHeap.push(array[i]); } } if (size%2==0)//偶数 { int tmp = minHeap.top(); minHeap.pop(); cout << "元素个数为偶数，中位数：" << tmp << " and " << minHeap.top() << endl; } else { minHeap.pop(); cout << "元素个数为奇数，中位数：" << minHeap.top() << endl; } }解决方案二：采用快速排序思想（分治法） 1、任意挑一个元素，以该元素为划分点，划分集合为两部分 2、如果左侧集合长度恰为 (n-1)/2，那么点恰为中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧，反之，中位数在左侧。进入相应的一侧继续寻找中位点
//前后指针法 int partion(int array[], int left, int right) { int pCur = left; int prev = pCur - 1; int key = array[right]; while (pCur <= right) { if (array[pCur] <= key&&++prev != pCur) std::swap(array[prev], array[pCur]); pCur++; } return prev; } void GetMidMum(int arr[],int size) { int left = 0; int right = size-1; int mid = size / 2; int div = partion(arr,left,right); while (div != mid) { if (div < mid)//有区间 div = partion(arr, div + 1, right); else div = partion(arr, left, div - 1); } cout << "中位数为：" << div << endl; }