我们把问题简化一下，给出的所有数都是0到1之间的小数。如果不是，也可以把所有数同时除以一个大整数从而转化为这种形式。我们依
然设立若干个桶，比如， 以小数点后面一位数为依据对所有数进行划分。我们仍然用链表把同一类的数串在一起，不同的是，每一个链表都是
有序的。也就是说，每一次读到一个新的数都要 进行一次插入排序。看我们的例子：
A[]= 0.12345, 0.111, 0.618, 0.9, 0.99999
+---+---+---+---+---+---+---+---+---+---+
十分位： | 0 | 1 |2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+-o-+---+---+---+---+-o-+---+---+-o-+ | | |
A[2]=0.111 A[3]=0.618 A[4]=0.9 | |
A[1]=0.12345 A[5]=0.99999
假如再下一个读入的数是0.122222，这个数需要插入到十分位为1的那个链表里适当的位置。我们需要遍历该链表直到找到第一个比
0.122222大的数，在例子中则应该插入到链表中A[2]和A[1]之间。最后，我们按顺序遍历所有链表，依次输出每个链表中的每个数。
这个算法显然是正确的，但复杂度显然不是线性。事实上，这种算法最坏情况下是O(n^2)的，因为当所有数的十分位都相同时算法就是一
个插入排序。和原来一样，我们下面要计算算法的平均时间复杂度，我们希望这种算法的平均复杂度是线性的。
这次算平均复杂度我们用最笨的办法。我们将算出所有可能出现的情况的总时间复杂度，除以总的情况数，得到平均的复杂度是多少。
每个数都可能属于10个桶中的一个，n个数总的情况有10^n种。这个值是我们庞大的算式的分母部分。如果一个桶里有K个元素，那么只与
这个桶有关的操作 有O(K^2)次，它就是一次插入排序的操作次数。下面计算，在10^n种情况中，K0=1
有多少种情况。K0=1表示，n个数中只有
一个数在0号桶，其 余n-1个数的十分位就只能在1到9中选择。那么K0=1的情况有C(n,1)*9^(n-1)，而每个K0=1的情况在0号桶中将产生1^2的复
杂度。 类似地，Ki=p的情况数为C(n,p)*9^(n-p)，复杂度总计为C(n,p)*9^(n-p)*p^2。枚举所有K的下标和p值，累加起来，这个 算式大家应
该能写出来了，但是这个……怎么算啊。别怕，我们是搞计算机的，拿出点和MO不一样的东西来。于是，Mathematica5.0隆重登场，我做数学
作业全靠它。它将帮我们化简这个复杂的式子。
我们遗憾地发现，虽然常数因子很小（只有0.1），但算法的平均复杂度仍然是平方的。等一下，1/10的那个10是我们桶的个数吗？那么
我们为什么不把桶的个数弄大点？我们干脆用m来表示桶的个数，重新计算一次：
化简出来，操作次数为O(n+n^2/m)。发现了么，如果m=Θ(n)的话，平均复杂度就变成了O(n)。也就是说，当桶的个数等于输入数据的个
数时，算法是平均线性的。
我们将在Hash表开散列的介绍中重新提到这个结论。
且慢，还有一个问题。10个桶以十分位的数字归类，那么n个桶用什么方法来分类呢？注意，分类的方法需要满足，一，一个数分到每个
桶里的概率相同（这样才 有我们上面的结论）；二，所有桶里容纳元素的范围必须是连续的。根据这两个条件，我们有办法把所有数恰好分为
n类。我们的输入数据不是都在0到1之间么？ 只需要看这些数乘以n的整数部分是多少就行了，读到一个数后乘以n取整得几就插入到几号桶里
。这本质上相当于把区间[0,1)平均分成n份。
问题七：有没有复杂度低于线性的排序算法
STOP! You should think for a while.
我们从O(n^2)走向O(nlogn)，又从O(nlogn)走向线性，每一次我们都讨论了复杂度下限的问题，根据讨论的结果提出了更优的算法。这次
总 算不行了，不可能有比线性还快的算法了，因为——你读入、输出数据至少就需要线性的时间。排序算
法之旅在线性时间复杂度这一站终止
了，所有十种排序算法到 这里介绍完毕了