9. 中位数和顺序统计量

顺序统计量，第i个顺序统计量指n个元素集合中第i小的元素。
最小值，第1个顺序统计量。
最大值，第n个顺序统计量。
中位数，第n/2个顺序统计量。（若n为偶数，取n/2-1）

我们可以通过一次遍历数组，取得最大值或者最小值。
但是若要取得中位数或者其他顺序统计量，则没办法通过一次遍历数组得到。
如果将数组排序，将可以直接得到中位数或者任意顺序统计量。由之前所学的排序算法可知，时间复杂度最好为Θ(nlgn)\Theta(n\lg n)
本章讨论如何在线性时间找到中位数或者其他顺序统计量。

期望为线性时间的选择算法

利用随机快速排序的思想，随机的挑选一个元素作为主元，并把数组分为两侧，一侧比主元小，一侧比主元大，如果主元的位置q就是想找的顺序统计量的位置i，则返回主元，否则继续递归的查找左侧数组或者右侧数组。伪代码如下：

随机选择算法

最坏情况为线性时间的选择算法

这个算法由几个大牛共同完成，发布在论文Time bounds for selection中。

中文描述如下：
https://www.jianshu.com/p/1c021beb5e72

涉及算法

点击查看实现

习题答案

练习

9.3-6

1
2
3
1. 如果k为1时，返回空数组
2. 如果k为偶数，找到数组的中位数,并把数组分为两组（比中位数大的一组，比中位数小的一组），递归解决这两个子问题，并把中位数以及两个字问题的解合并返回
3. 如果k为奇数，找到数组中间的两个分位数left和right，并把数组分出两组（比left小的一组，比right大的一组），递归解决这两个子问题，并把left right以及两个字问题的解合并返回

9.3-7

1
2
3
4
1. 线性时间找到中位数
2. 线性时间算出每个元素和中位数的距离（|x-middle|）
3. 线性时间找到第k小的距离
4. 线性时间找出比k小的距离对应的元素

9.3-8

1
2
3
1. 选择X Y两数组的中位数作为主元Xk和Yk
2. 比较Xk和Yk，如果Xk大于Yk，则取Xk左侧的元素作为新的X数组（包括X），取Yk右侧的元素作为新的Y数组（包括Y）
3. 重复1 2 两部，直到每个数组只剩两个元素，剩下的四个元素中第二小的便是两数组的中位数