一个会计师负责对一个小饭店的账本进行审核。每天晚上饭店打烊时，饭店主人记录白天的总销售额，然后打印出有总额和日期的收据。这些收据存放在一个大盒子里面。每年年终，会计师审核盒子中的这些收据，检查是否有的已经丢失。你能想象，盒子中的收据都是无序状态的。
会计师可以按照日期降序地排列所有的收据，然后审核。另一种方法是，他找到一个当年的空白日历，从盒子中一条接一条取出收据来，然后在日历上相应日期用X标记。一旦盒子为空之后，会计师仅仅需要检查一下日历上哪些日子没有标记。注意第二种方法中，从来没有两个收据会相互进行比较。如果饭店已经营业了60年，并且会计师有60年的日历，如果盒子中只有5张收据，那么这个方法将会非常低效；但是有20 000张收据的话，这将是一个有效的方法。收据的数量与总日子的比例决定了方法的效率。
在本章开头，我们证明了基于比较的排序算法不可能好于O(n log n)的时间排序元素。令人惊异的是，如果能知道这些元素的更多信息，那么就会有其他的排序方法。例如，假设你被指定排序n个元素，并且告知你每一个元素的值范围都在[0,k)之间，k比n小得多。你就能够利用这个信息，使用一个线性的排序算法，叫做计数排序。
使用环境
计数排序，如图4-17所示，不需要一个比较函数，是对范围固定在[0,k)的整数排序的最佳选择。即使k个元素的全序能够被决定以及每一个元素的值都是唯一的，这个算法也可用。例如，如果排序一系列形如1/p（p为整数）的小数，p的最大值为k，那么每个小数1/p能够被分配一个唯一的值k-p。
图 4-17 计数排序详解