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:

涉及算法

点击查看实现

• 计数排序