比较排序的时间下界

合并排序和堆排序在最坏情况下能够在O(nlgn)时间内排序n个数， 而快速排序则能够在平均情况下达到这个上界。 这些算法在确定元素的次序时， 都是基于元素间的比较。 这类排序算法称为__比较排序__。

比较排序的时间下界是O(nlgn)， 这意味着所有的基于比较的排序算法，在最坏情况下都要用$\Omega (n \lg n)$ 次比较来完成排序。

这是因为比较排序可以被抽象为__决策树__， 决策树是一棵满二叉数， 它的每一条从根节点到叶节点的路径都对应于比较排序的一次执行过程， 达到叶节点时，叶节点确定了这次排序的结果。 所以比较排序算法的最坏情况的比较次数等于决策树的高度。 n个数的排列总数有n!，每一种排列都必须在决策树的叶节点中出现， 高度为h的决策树的叶节点个数最多为$2^h$，故有：

$$n! \leq 2^h \\ \Longrightarrow h \geq \lg (n!) = \Omega (n \lg n)$$

所以比较排序的时间下界是O(nlgn)。

通过计数排序实现线性时间排序

如果已经知道n个元素都是来自于0到k的整数， 其中$k = O(n)$, 那么可以通过统计0到k中的每一个数在n个元素中出现的次数来达到排序的目的。 计数排序的运行时间为 $\Theta (n)$。

书上在实现计数排序时，

1. 首先遍历一遍原数组A，将各个元素出现次数统计到数组C中,此时C[0..k]的每一项C[i]表示i在A中的出现次数
2. 然后遍历一遍数组C, 使C[i]表示A中小于或等于i的元素个数
3. 最后遍历A(逆向遍历)，把结果放到数组B中，把A[i]放到B的C[A[i]]位置上，同时把C[A[i]]减1 (这是为了把重复的元素放到不同的位置上去)

其实只需要让C[i]记录i在数组A中出现的次数，然后遍历一遍数组C就可以输出排序的结果。 具体遍历方法如下：

j <- 1
for i <- 1 to k
    while C[i] > 0
        do C[i] <- C[i] - 1 
            A[j] = i
            j <- j + 1

就能把排序好的结果保存到A中，不需要另外的数组B。 但是书上的这种方法有一个好处，它能保证排序是__稳定__的。 也就是说，具有相同值的元素在输出数组中的相对次序与输入数组中的相对次序一样。 因为是采取对A的逆向遍历，两个相同的元素中，位置靠前的元素后被遍历，此时C[i]已经变小了， 所以也会被放在更靠前的位置。稳定排序的好处在于它能够保证基数排序的正确性。

基数排序：另一种线性时间排序

基数排序主要解决的问题是对于多位整数的排序问题。 比如有n个d位数，每一位可以取k个不同的值，要对它进行排序， 一般的想法是先对最高位进行排序， 然后对于高位相同的子数组按次高位进行排序，依次类推。 这种想法的好处在于如果两个数中高位较大的数一定较大， 所以很容易把各个子数组的排序结果进行合并。比如排序10进制的三位数， 3XX一定都大于2XX，所以把2XX的子数组放在3XX的子数组前面就能保证合并结果的有序性。 但是它的不好的地方在于需要维护大量的子数组(随着递归的深度加深，子数组个数增多)， 这对于原始的基于纸带的排序的是不可行的。

那有没有一种排序方法，既能使后面的排序利用到前面排序的结果， 而且能够不需要维护大量的子数组呢？基数排序就是这样一种排序方法， 它先把数组按最低位进行排序，然后再对结果按次低位进行排序，依次类推。 每一次的排序都必须是__稳定排序__，这样能保证在按某位进行排序之后， 整个数组在从该位到最低位的子序列上都是有序的，可以通过一个简单的归纳加以证明。

同时，在对n个b位数进行排序时，每次可以按r位进行排序， 而不仅仅是1位，这样能够在$\Omega ((b/r)(n + 2^r))$的时间内完成对数组的排序。 可以选取适当的r达到最好的时间性能。

同时找出数组中的最大值和最小值

从一个数组中找出最大值或者最小值需要n-1次比较， 比如寻找最大值，首先将最大值设为第一个元素的值， 然后让n-1个元素和最大值进行比较，如果大于最大值， 就将最大值设为它，一共需要n-1次比较。

而如果是同时找出最大值和最小值呢， 当然可以分别按上面的方法找出最大值和最小值， 一共需要的比较次数是2n-2。

书上给出了另外一种方法： 成对的处理元素，将较小者与最小值相比，较大者与最大值相比， 这样能将比较次数降为$3 \lceil n/2 \rceil$。

在线性时间内选出数组中的第i小元素

书上给出了两种方法：

第一种方法利用随机化快速排序算法中的RANDOMIZED-PARTITION函数对数组进行划分，然后根据 i是在哪一个部分中去相应部分中进行查找，这种方法能保证运行时间的期望是线性，代码如下：

def RANDOMIZED-SELECT(A, p, r, i)
    q <- RANDOMIZED-PARTITION(A, p, r)
    k <- q - p + 1
    if i = k
        then return A[q]
    elseif i < k
        then return RANDOMIZED-SELECT(A, p, q-1, i)
    else return RANDOMIZED-SELECT(A, q+1, r, i-k)

简单说明一下在划分的两个子数组中，如果有一个长度为0， 为什么不会它调用RANDOMIZED-SELECT:

• 如果子数组A[p..q-1]长度为0，则q = p，k = q - p + 1 = 1，$i \geq k$, 不会对这个子数组调用RANDOMIZED-SELECT
• 如果子数组A[q+1..r]长度为0，则q = r，k = r - p + 1 = length[A]，$i \leq k$, 不会对这个子数组调用RANDOMIZED-SELECT

第二种方法通过保证每次的划分是一个好的划分保证算法的线性时间。 具体的划分方式是：

1. 将数组的n个元素划分为 $\lceil n/5 \rceil$组，除最后一组之外，其余都有5个元素
2. 对每一组找到其中位数, 首先对每个数组进行插入排序，然后找到其中的中位数
3. 通过递归调用SELECT函数(就是找出数组中第i小元素的函数)，找到这些中位数中的中位数x
4. 以x作为划分元素对数组进行划分

这个划分是一个好的划分， 因为能保证划分出来的两个子数组中任意一个的长度都不会超过某一个特定值。 在$\lceil n/5 \rceil$个组中， 假设所有的中位数组成数组B[1..m]，其中 $m = \lceil n/5 \rceil$, 假设x = B[k]，k = $\lceil \frac{1}{2} \lceil \frac{n}{5} \rceil \rceil$, 在所有中位数在A[k..m]的组中，除去最后一组和x所在的组之外，其他的组至少有3个元素大于x， 所以大于x的元素个数至少为：

$$3(\lceil \frac{1}{2} \lceil \frac{n}{5} \rceil \rceil - 2) \geq \frac{3n}{10} - 6$$

类似的小于x的元素个数至少有$\frac{3n}{10} - 6$个， 所以至多有$\frac{7n}{10} + 6$个元素被递归的调用SELECT， 有了这个结论之后就能保证SELECT函数可以在线性的时间内完成。