9. 中位数和顺序统计量

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

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

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

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

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

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

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

涉及算法

点击查看实现

• 随机选择算法（RANDOMIZED_SELECT）

习题答案

练习

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 两部，直到每个数组只剩两个元素，剩下的四个元素中第二小的便是两数组的中位数

留言與分享

8. 线性时间排序

前边介绍了很多排序算法，他们有一个共同点：元素的排序依赖于对他们之间的比较，这类排序我们称其为比较排序。本章节讨论比较排序的下界以及一些线性时间的排序方法。

比较排序的下界

将比较排序抽象为一颗决策树。
下图为三个元素排序的一颗决策树，叶子节点表示比较结果，其他节点表示某两个元素$(a,b)$作比较，节点的左子节点表示$a<=b$，节点的右子节点表示$a>b$。可以发现叶子节点包含了三个元素比较的所有可能情况，而且从根节点到叶子节点用了最少的比较次数。

接下来我们考虑n个元素排序的情况，因为n个元素排序可能会有n!种情况，所以叶子节点树小于等于n!，而这个树高度表示需要最坏情况的比较次数。

$h >= \lg(n!) = \Omega(n\lg n)$

所以在最坏情况下，任何比较排序算法都需要做$\Omega(n\lg n)$次比较。

计数排序

假设n个元素都是0~k之间的整数，而且$k=\Omicron(n)$时，计数排序的运行时间为$\Theta(n)$。

计数排序的基本思想为，首先得到0~k每一个值对应多少个元素，然后推算出每一个值对应元素在输出数组上的位置范围，最后将各个元素放到应该的位置。
计数排序的伪代码和处理过程如下图所示：

基数排序

基数排序的思想为，将带排序的数看做d位数，每一位的取值有K个可能，然后把待排数组从最低位开始做稳定排序（当有相同的数值时，排序后他们的顺序不变），一位接着一位直到最高位。伪代码，以及一个三位十进制数的排序过程如下：

如果基数排序使用的稳定排序方法耗时为$\Theta(n+k)$，每个数为d位，那么基数排序的时间复杂度为$\Theta(d(n+k))$

桶排序

TODO:

涉及算法

点击查看实现

• 计数排序

留言與分享