如何在不排序的情况下求数组中的中位数？

Nen 2022-03-28 13:53

- 程序员

根据定义，如果数组是一个已经排序好的数组，那么直接通过索引即可获取到所需的中位数。如果题目允许排序，那么本题的关键在于选取一个合适的排序算法对数组进行排序。一般而言，快速排序的平均时间复杂度较低，为O(Nlog2N)，所以，如果采用排序方法，算法的平均时间复杂度为O(Nlog2N)。

可是，题目要求，不许使用排序算法。那么前一种方法显然走不通。此时，可以换一种思路：分治的思想。快速排序算法在每一次局部递归后都保证某个元素左侧的元素的值都比它小，右侧的元素的值都比它大，因此，可以利用这个思路快速地找到第N大元素，而与快速排序算法不同的是，这种方法关注的并不是元素的左右两边，而仅仅是某一边。

根据快速排序的方法，可以采用一种类似快速排序的方法，找出这个中位数。具体而言，首先把问题转化为求一列数中第i小的数的问题，求中位数就是求一列数的第（length/2+1）小的数的问题（其中length表示的是数组序列的长度）。

当使用一次类快速排序算法后，分割元素的下标为pos。

1）当pos＞length/2时，说明中位数在数组左半部分，那么继续在左半部分查找。

2）当pos==lengh/2时，说明找到该中位数，返回A[pos]即可。

3）当pos＜length/2时，说明中位数在数组右半部分，那么继续在数组右半部分查找。以上默认此数组序列长度为奇数，如果为偶数则调用上述方法两次找到中间的两个数求平均值。示例代码如下：

程序的运行结果为：

算法性能分析：这种方法在平均情况下的时间复杂度为O(N)。

如何在不排序的情况下求数组中的中位数？

轩辕小不懂的其他提问

类似问题

如何在不排序的情况下求数组中的中位数？

轩辕小不懂 的其他提问

类似问题

轩辕小不懂的其他提问