数据结构（邓俊辉）学习笔记】词典 05——桶排序和计数排序

1. 桶排序

1.1大数据 + 小范围

作为散列思想的一个具体应用实例，我们来学习桶排序算法，以及相应的计数排序算法。有意思的是这类算法的性能已经不再完全取决于输入的规模，也就是待排序序列的长度 n，同时也取决于待排序元素的取值范围，通常记作 M。

不失一般性，可设为是从 0 到 M 的一个整数区间。没错 M， 你应该记得我们曾经用它来表示过散列表的长度。事实上新算法的渐进时间复杂度将是 O （n + M)， 或者等效的，取决于 O （ max（n ， M）)。

因此，待排序元素的取值范围越是有限，这种算法的优势也就越是明显。

比如在很多应用中元素的取值范围都会不超过 O（n），当然，这也意味着在输入元素中存在的大量的重复。
  ~  

若果真如此，新的算法就有望在线性的时间内完成排序。

我们来考察对一组英文大写字母的排序问题。
  ~  
这类问题，通常都满足 M = 26 << n，故存在大量的重复。
  ~  
比如这一行就是输入的待排序列 ( vector [] )，而这一行则是对应的排序列( Sorted [] )。我们现在就来看看如何采用桶排序和计数排序算法完成这一有序化的任务。首先不妨来感受一下。
  ~  
蓝色折线，对应于输入的随机序列。红色折线，对应于输出的排序序列。后者必然单调。

无论输入序列如何变化，我们的算法总是可以正确地完成有序化的任务。那么这里的桶排序和计数排序究竟是如何工作的呢？其原理又是怎样的呢？

1. 2. 桶排序

这里最基本的一个思路就是运用散列表。在这里既然考虑的只是英文字母，所以各元素的取值无非26种可能。因此我们只需将表长 M 取作为 26。并相应的建立这样一个散列表，而其中的各个桶单元则依次对应于 a，b，c 一直到 z， 这26个字母。

在建立了这样一个散列表之后，我们的第一项任务就是来填充名为 count 这一行。顾名思义，其中的每一个元素都是一个计数器，分别记录其所对应的那个字母在输入序列中所出现的次数。

比如这个2就意味着对应的字母 G ，在输入序列中总共出现了两次，相应的 B 只出现了一次。而 A、H、K 之类的字母根本就没有出现。当然这里的5，也意味着 M 在输入序中总共出现了5次。

那么由输入序列如何快速地得到这样一张统计表呢？我说如果输入的规模为 n，那么我们应该可以在 O（n） 的线性时间内完成这个任务。你能想出具体的方法吗？

没错，只需遍历一次整个输入集。在此过程中，每遇到一个字符就对它所对应的那个计数器做累加。形象地说，这样的过程就犹如将所有的元素分别扔到它所对应的桶单元中，因此这一步骤也称作分配 distribution。

这图中请留意蓝色的折线，它是什么呢？没错，这条折线恰恰就对应于刚才我们的统计结果。然而，这还不是我们最终所需要的，我还需要什么呢？这条红色的折线，此前的那条蓝色折线被称作 count，是因为它反映了各字符在输入序列中出现的次数。而新的这条红线，这称作 accumulation，这暗示着它是某种累计值。没错，累计值。

更精确的说，这条红色折线上的任何一个点其实都对应于蓝色折线至此之前的所有数值的积分。既然蓝色折线是非负的，所以作为它的积分，这条红色折线是单调非降的。那么红色折线上的这样每一个积分值具体又是什么含义呢？

2. 计数排序

2.1 计数排序

没错，根据我们此前的定义，这个积分值也就是包括它所对应的那个字母在内，以及相对而言更小的那些字母，在输入系列中所出现次数的总和。而这个总和也就给出了对应的这个字母在有序的输出序列中所对应的位置，或者更一般的，如果这个字母出现多次，也就是它在最终有序列中所分布的区间。

这里的字母 F 为例，它总共出现了一次，而对应的积分值为6。这就说明在输入序列中，小于 G 的字母应该恰为6个。因此，作为这些字母中的最大者 F，也自然应该被放在编号为5的位置。没错，5，因为从 0 到 5 恰好是 6 个小于 G 的字母。

而同样的道理，因为字母 G 所对应的积分值为 8，所以输入序列中的这两个字母 G ，在最终的有序序列中，自然地也就应该被归入至【6，8)的这个区间了。具体的也就是6和7这两个单元。

由此可见，只要我们能够得到每个字母的统计值以及累计值，就可以根据相邻字母的累计值，确定其在输出序列中所应处的区间范围。

刚才已经分析过，散列表 count 可以在线性时间内计算而得。那么，累计值散列表 accumulation呢？我说它的建造只需要 O( m) 的时间，也就是说每个单元只需常数，你能看出具体的算法吗？

是的，只需从头到尾线性扫描一遍即可。

首先是字母 A 所对应的第一个桶单元， 我们可以直接用他的统计值作为它的累计值。接下来是字母 B，我们可以在 A 的积分值的基础上累计上 B 的统计值，从而得到 B 的积分值。再接下来的字母 C 也是如此，也就说将 B 的积分值再加上 C 的统计值，也就得到了 C 的积分值。以下完全同理。

由此可见，整个的计算过程无非是从第一个字母开始，依次的向后递推，而每一步递推的算法模式都是一样的，也就是将前一项累计上后一项的统计值，从而得到后一项。累计更新。