要解决这个问题首先要了解什仫是中位数，所谓的中位数就是在一组有序的数字中找到中间的那个数字。如果数字的个数是奇数则直接返回中间的那个数，如果数字的个数是偶数此时这组数据的中位数有两个，取中间两个数的平均值即可。
想法一、不论用什仫排序算法使得该组数据有序，直接取中间值即可。
这种只要你掌握常见的排序算法就可以了，在这里就不实现了。
想法二、利用快排的思想
1、先进行一趟快排，使得div左边的值都比arr[div]小，div右边的值都比arr[div]大，但是这个div的位置是不确定的，可能位于中间，也可能偏左或者偏右。
2、计算出mid所在的下标，如果是奇数则是mid=(size+1)/2，如果是偶数则是mid=size/2。
3、此时需要比较mid和div所在的位置。如果mid在div所在位置的左边，此时就要递归去左半区间查找；如果mid在div的右边，此时就要递归去右半区间查找；如果恰好相等则说明div/mid所在的位置就是中位数。
代码实现如下：
int PartSort(int *arr, int start, int end)
{
int left = start;
int right = end;
int key = arr[end]; //选取关键字
while (left < right)
{
while (left < right && arr[left] <= key) //左边找比key大的值
{
++left;
}
while (left < right && arr[right] >= key) //右边找比key小的值
{
--right;
}
if (left < right)
{
swap(arr[left], arr[right]); //找到之后交换左右的值
}
}
swap(arr[right], arr[end]);
return left;
}
//求一个无序数组的中位数
int GetMidNumNoSort1(int *arr,int size)
{
assert(arr);
int start = 0;
int end = size - 1;
int mid = (size - 1) / 2;
int div = PartSort(arr,start,end);
while (div != mid)
{
if (mid < div) //左半区间找
div = PartSort(arr, start, div - 1);
else //左半区间找
div = PartSort(arr, div + 1, end);
}
return arr[mid]; //找到了
}想法三、建堆的思想
1、如果数组元素的个数是奇数，取数组前(size+1)/2个元素建堆，如果是偶数则取前 size/2 个元素建堆。
2、建完堆之后，此时堆顶的元素是这前 (size-1)/2 个元素中最小的；此时需要将数组中剩余的元素分别和堆顶的元素进行比较：如果小于等于堆顶元素则直接丢弃，如果大于堆顶的元素则需要更新堆顶的元素并重新调整堆的结构，使其保证小顶堆的特性。
3、将剩余的元素全部比较完之后，此时堆顶的元素就是所要求的中位数。
在这里需要提到的是，优先级队列的底层也是通过建堆来实现的。默认是建大堆，此时就要编写一个使其建小堆的仿函数了，其实也就是相当于修改了它的优先级。
代码实现如下：
//建小堆来实现
#include<queue>
#include<vector>
int GetMidNumNoSort2(int *arr, int size)
{
assert(arr);
int len = (size + 1) / 2; //奇数个元素
//int len = size / 2;
struct Compare //建小堆
{
int operator()(int left, int right)
{
return left > right;
}
};
priority_queue<int, vector<int>, Compare> heap;
//先以整个数组的前len个元素建小堆
for (int i = 0; i < len; i++)
{
heap.push(arr[i]);
}
for (int i = len; i < size; i++)
{
if (arr[i] > heap.top()) //比堆顶元素大则更新该小堆
{
heap.pop();
heap.push(arr[i]);
}
}
if (!heap.empty())
{
return heap.top();
}
}在这里就分享结束了，以上仅是我个人的想法，也通过了奇数数组个数和偶数数组个数的测试，不喜勿喷！！！