题目：求出一个无需数组的中位数。
例：{2,5,4,9,3,6,8,7,1}的中位数为5，{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。 要求： 不能使用排序。 思路1：将数据平均分配到最大堆和最小堆中，并且保证最小堆中的数据存放的数据都比最大堆中是数据大，那么此时最小堆堆顶的元素一定是中位数。 那么如何保证最小堆中的元素，都比大堆中的元素大 (1)遍历数组，将第i个数插入堆中，i为奇数时，插入最小堆，i为偶数时插入最大堆。(最大堆的插入的数据比较大) (2)每次插入时，将最大堆和最小堆的堆顶交换。
struct greater { bool operator()(int x, int y) { return x > y; //x,小的优先级高 } }; void GetMidNumNoSort1(int arr[], int size) { priority_queue<int> max_heap; priority_queue< int, vector<int>, greater > min_heap; for (int i = 0; i < size; ++i) { //i是从0开始的，所以max存放的数据比较多 if ((i & 1) == 1) min_heap.push(arr[i]); else max_heap.push(arr[i]); //每次交换最大堆和最小堆中的数据，保证最小堆中的数据大于最大堆中 if (!min_heap.empty() && !max_heap.empty()) { int temp = min_heap.top(); min_heap.pop(); max_heap.push(temp); temp = max_heap.top(); max_heap.pop(); min_heap.push(temp); } } if ((size & 1) == 0)//偶数 cout << "中位数：" << max_heap.top() << " " << min_heap.top() << endl; else cout << "中位数：" << max_heap.top() << endl; }思路2： (1)将前(n+1)/2个元素调整为一个小顶堆 (2)对后续的每一个元素，和堆顶比较，如果小于等于堆顶，丢弃之，取下一个元素。 如果大于堆顶，用该元素取代堆顶，调整堆，取下一元素。重复这个步骤 (3) 当遍历完所有元素之后，堆顶即是中位数。
void GetMidNumNoSort2(int arr[],int size) { priority_queue< int, vector<int>, greater<int> > min_heap; int count = (size + 1) >> 1;//位运算，相当于/2 //存放count个数，比如5个元素，存放3个 for (int i = 0; i <= count; ++i) min_heap.push(arr[i]); for (int i = count + 1; i < size; ++i) { int temp = min_heap.top(); if (arr[i] > temp) { min_heap.pop(); min_heap.push(arr[i]); } } if ((size & 1) == 1)//奇数 { min_heap.pop(); cout << "中位数：" << min_heap.top() << endl; } else { int tmp = min_heap.top(); min_heap.pop(); cout << "中位数：" << tmp <<" "<< min_heap.top() << endl; } }思路3：任意挑一个元素，以该元素为支点，划分集合为两部分，如果左侧集合长度恰为 (n-1)/2，那么支点恰为中位数。如果左侧长度小于(n-1)/2, 那么中位数在右侧，反之，中位数在左侧。 进入相应的一侧继续寻找中位数。
//挖坑法 int PartSort(int arr[], int left,int right) { int key = arr[right]; while (left < right) { //key右边，先从左找比key值大 while (left < right && arr[left] <= key) ++left; if (left < right) { arr[right] = arr[left]; --right; } //从右找比key小 while (left < right && arr[right] >= key) --right; if (left < right) { arr[left] = arr[right]; ++left; } } arr[left] = key; return left; } void GetMidNumNoSort3(int arr[],int size) { int left = 0; int right = size - 1; int mid = size / 2; int div = PartSort(arr, left, right); while (div != mid) { if (div < mid)//右半区间 { div = PartSort(arr, div + 1, right); } else { div = PartSort(arr, left, div - 1); } } cout << "中位数" << arr[div] << endl; }