006【算法篇】线性时间排序

前面我们提到的插入排序、归并排序及快速排序均有个特点，即时间复杂度渐近下界为𝛺(nlgn)，哪怕是随机化的快速排序也是如此。

这些排序算法有个特点，即都是基于「比较」模型而衍生的算法，都是通过某种「比较元素」的方式最终实现了排序。由此我们是否可以得出结论：所有基于「比较」模型的算法，其时间复杂度的渐近下界均为𝛺(nlgn)？

答案是肯定的，具体证明过程如下：

假设我们基于「比较」模型来针对输入数据进行排序时，一定会产生诸如这样的判断逻辑，然后依照这些判断逻辑作进一步的决策。这些判断逻辑形成了如下的一棵决策树

WechatIMG206.png

由图我们可知，假设输入数据有n个节点，决策树的高度为h，叶节点为所有可能的排列结果；那么最终形成排序结果时的比较次数即为决策树的高度，因为每比较一次就深入一层，即高度加1。

由于决策树也是一棵二叉树，根据二叉树的性质，假设二叉树的叶节点个数为m，我们立即有如下结论：

• 高度为h的二叉树中，叶节点的总数至多为，即：
• 由于决策树的叶节点包括了输入数据所有的排列情况，那么叶节点的总数理应至少为n!，即：

故有如下不等式：

针对(1)式两边取对数，并化简计算：

证毕。其中(2)式引用了斯特林公式。

那么由此是否可以证明，所有的排序算法渐近下界均为𝛺(nlgn)呢？答案是否定的，人类对速度的极致追求怎么可能停留在𝛺(nlgn)这样一个难以接受的程度？可以进一步提升排序速度，使之趋近于线性时间吗？因为就目前已知的软硬件情况下来，无论如何也要遍历完全部的元素，所以极限排序速度也应该是在线性时间内完成。

答案是肯定的，但是也需要付出一定的代价。

---

计数排序

这是一个最简单的线性时间排序，针对元素值不是很大时比较有效，它需要额外的内存开销用于存储排序结果以及计数缓存。

计数排序的思想是，针对每个输入元素x，如果我们能够确认比x小的元素个数，那么排序结果中我们把x放在输出数组对应的位置即可。例如假设有17个元素比x小，那么就把x放在输出数组的第18个位置上即可。下面给出伪代码：

COUNTING_SORT(A,B,k)
    //let C[0..k] be a new array
    for i=0 to k
        C[i]=0
    for j=1 to A.length
        C[A[j]]=C[A[j]]+1       // C[j]的值为元素值为A[j]的个数
    for i=1 to k
        C[i]=C[i-1]+C[i]        // C[i]的值为元素值小于等于A[i]的个数
    for j=A.length down to 1
        B[C[A[j]]]=A[j]
        C[A[j]]=C[A[j]]-1

举例说明，假设输入数据A=[4，1，3，4，3]，我们作图来表示整个排序过程如下：

WechatIMG207.png

下面我们来分析计数排序的时间复杂度。显然第3-4行代码所需的时间为𝛩(k)，5-6行代码所需时间为𝛩(n)，7-8行代码所需时间为𝛩(k)，9-11行代码所需时间为𝛩(n)，这样总的时间代价为𝛩(n+k)。

所以在实际工作中，当k=𝛰(n)时我们可以选择计数代码，因为它的时间复杂度为𝛩(n)，能够在线性时间内完成，但是其空间复杂度较高，需要两个数组的内存空间。

当k值远大于n时，就不建议用这个算法了……除非你的内存无限大。

基数排序

基数排序的算法就不讲了，比较简单，伪代码如下：

RADIX_SORT(A,d) //d表示数组元素的位数，其中1为最低位，d为最高位
    for i=1 to d
        //进行d轮排序，每轮排序基于位数i

每轮的辅助排序算法不建议使用基于「比较」模型的算法，因为这样会使得时间复杂度为𝛺(nlgn)，违背我们的初衷，所以我们想到了使用计数排序，因为它是基于线性时间的，而且属于是稳定的算法，只要k值选择合理。

下面我们重点分析下时间复杂度，以及k的选择。

一般不建议按位进行逐轮排序，我们假设待排序的数字至多为b位数，如果是按位进行排序的话，那么所需时间为𝛺(n*b)。如果b=lgn的话，那么其时间正好为𝛺(nlgn)，这不是我们想看到的。所以一般在处理的时候不会按位进行排序，一般会灵活地分解为小于b的若干块进行排序。

由于任何数在计算机内的表示均最终为二进制数，下文中我们仅讨论所排序的数字为二进制数的情况。

假设我们有n个待排序的二进制数，该二进制数的位数为b，那么我们可以拆分为d=b/r的r位进行d轮排序，其中每位为r比特，可表示的数字范围为，这个数也相当于计数排序中的k值，于是时间复杂度计算如下：

于是，问题就变成了如何选择r的值，使得(3)式中的一元函数取最小值……于是乎，我们马上就想到了高数的求导，我们对r进行求导，针对导数为0的情况求出r的值即可。具体求导过程就不写了，比较简单，下面我们用另一种思路来推理。

从(3)式中我们可以分析，r的值一定要能够使得 (b/r)*n的值足够小，因为这样可以减少排序的轮数，这样的话会要求r的值越大越好；但是同时不能太大，因为太大的话会导致的值飙升，适得其反，因此会要求n的值大于，也即：r应该比lgn要小，所以我们得到了r的一个上界，即r=lgn，这个取值应该跟函数求导的值一样的。于是乎当r=lgn时的时间复杂度为：

显然，这是线性时间内的排序，但是需要付出位的辅助空间。算法很美，但是用起来需要细细考究。