【出自WR面试题】
难度系数：★★★★☆ 被考察系数：★★★★☆
题目描述：
所谓中位数就是一组数据从小到大排列后中间的那个数字。如果数组长度为偶数，那么中位数的值就是中间两个数字相加除以2；如果数组长度为奇数，那么中位数的值就是中间那个数字。
分析与解答：
根据定义，如果数组是一个已经排序好的数组，那么直接通过索引即可获取到所需的中位数。如果题目允许排序的话，那么本题的关键在于选取一个合适的排序算法对数组进行排序。一般而言，快速排序的平均时间复杂度较低，为O（NlogN），所以，如果采用排序方法的话，算法的平均时间复杂度为O（NlogN）。
可是，题目要求不许使用排序算法。那么前一种方法显然走不通。此时，可以换一种思路：分治的思想。快速排序算法在每一次局部递归后都保证某个元素左侧的元素的值都比它小，右侧的元素的值都比它大，因此，可以利用这个思路快速地找到第N大元素，而与快速排序算法不同的是，这种方法关注的并不是元素的左右两边，而仅仅是某一边。
根据快速排序的方法，可以采用一种类似快速排序的方法，找出这个中位数。具体而言，首先把问题转化为求一列数中第i小的数的问题，求中位数就是求一列数的第（length/2+1）小的数的问题（其中length表示的是数组序列的长度）。
当使用一次类快速排序算法后，分割元素的下标为pos：(www.xing528.com)
（1）当pos＞length/2时，说明中位数在数组左半部分，那么继续在左半部分查找。
（2）当pos==lengh/2时，说明找到该中位数，返回A[pos]即可。
（3）当pos＜length/2时，说明中位数在数组右半部分，那么继续在数组右半部分查找。
以上默认此数组序列长度为奇数，如果为偶数就是调用上述方法两次找到中间的两个数求平均值。示例代码如下：
程序的运行结果如下：
6
算法性能分析：
这种方法在平均情况下的时间复杂度为O（N）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
