普通排序VS计数排序
下面我们将通过对比两种排序算法来验证上面的结论，其中一个是标准的Java排序程序，另一个则是根据具体情况定制化的排序程序。第一个例子是简单的对n个正整数排序，数值在0到k之间。在Java中我们可以通过简单的使用Collections(集合)或Arrays(数组)类来实现这个目的，如下例所示：
2 * 使用Collections的sort方法来对输入的正整数进行排序
3 */
4 public ArrayList<Integer> sortInts(ArrayList<Integer> inputSequence)
5 {
6 Collections.sort(inputSequence);
7 return inputSequence;
8 } /**
9
10
11 *使用Arrays类来对一个整数数字进行排序
12
13 */
14 public int[] sortInts(int [] inputSequence)
15 {
16 Arrays.sort(inputSequence);
17 return inputSequence;
18 }
在Java文档中这样描述Collections.sort程序：
“该排序算法是一个经过修改的合并排序算法(其中如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并)。此算法提供可保证的n log(n)性能。 此实现将指定列表转储到一个数组中，并对数组进行排序，在重置数组中相应位置处每个元素的列表上进行迭代。这避免了由于试图对适当位置上的链接列表进行排序而产生的n2 log(n)性能。”
Collections.sort程序被设计可以支持任意元素类型，因此这个排序算法不能利用我们例子中专门针对正整数排序的一些特点。而Arrays.sort程序的文档描述则显示它是一个更适合对整数进行排序的算法：
“将特定的整数数组进行排序，得到一个有序整数数组。该排序算法是一个经过调优的快速排序法，改编自Jon L. Bentley和M.Douglas McIlroy合著的《Engineering a Sort Function", Software-Practice and Experience》 Vol. 23(11) P. 1249-1265 (November 1993)。此算法在许多数据集上提供 n*log(n) 性能，这导致其他快速排序会降低二次性能。
这个Arrays.sort算法已经针对整数排序进行了改进，与我们本例中的特定要求已经更接近了一步，因此它的效率要比Collections.sort更高一些。但是，O(nlogn)的性能依然非常高，我们还有方法来改进它。
现在，如果我们要专门针对正整数来设计一个最优化的排序程序， 那么我们要记住整数类型具有以下特点：
1、与实数或浮点数不同的是，两个相邻整数之间没有其它整数。例如有两个整数a和b，如果a+1=b，那么你不可能再找到第三个整数x能满足a
2、这些整数没有关联数据，它们不是元组(tuples)。因此在排序过程中，同样大小的元素可以不用重复排序过程，这可以提高效率。
考虑到我们输入序列具有以上两个特点，我们可以编写一个非常不同的排序程序，计数排序的改进版，如Listing 1所示。
listing1
2 * 实现计数排序算法
3 */
4 public int[] countingSort(int[] inputSequence)
5 {
6 // 获得最大值
7 int maxValue = -1;
8 for(int i = 0; i < inputSequence.length; i++)
9 {
10 int x = inputSequence[i];
11 if(x > maxValue)
12 {
13 maxValue = x;
14 }
15 }
16
17 // 指定一个数组
18 int[] counts = new int[maxValue + 1];
19
20 // 计算输入序列中每一个数出现的次数
21 for(int i : inputSequence)
22 {
23 counts[i] += 1;
24 }
25
26 // 获得排序数字序列
27 for(int i = 0, j = 0; i <= maxValue; i++)
28 {
29 int c = counts[i];
30 for(int k = 0; k < c; k++, j++)
31 {
32 inputSequence[j] = i;
33 }
34 }
35
36 return inputSequence;
37 }
下面我们来简单对这个程序的算法进行介绍，这个程序首先获得输入序列中最大的数值k，并以它为最大下标来创建一个数组(长度为k+1)。然后再次检查输入序列，并确定每一个数值在序列中出现的次数，并将其记录在counts数组中相应下标位置。举个例子来说，如果输入的数值序列是[3,1,4,7,1,4,0],那么我们将得到一个长度为8的计数数组counts[]，包含下列值[1,2,0,1,2,0,0,1]。最后程序根据计数数组来重写输入数列inputSequence。在这个例子中得到的数值是[0,1,1,3,4,4,7] 。
从以上算法中我们可以明白为什么这个算法不能用来对实数或浮点数进行排序;因为它们的输入序列中的最大数值不能告诉我们要创建多少长度的技术数组，而且这个计数排序也不能用来对整数键值的元组进行排序，因为算法执行最后一步的时候，重写了最初的输入元素，破坏了元素的最初数值。
这个改进版的计数排序算法对输入序列共进行了三次遍历：第一次是发现其最大值(即k)，这个操作的时间复杂度是O(n)。它分配了一个最大下标为k的数组，尽管这只是一个简单的数组指定操作，我们也认为它的时间复杂度为O(k)。然后它第二次对输入数值进行遍历，来计算不同数值出现的次数。最后它使用排序的序列来对覆盖原始输入序列，时间复杂度为O(n)。因此这个算法总的时间复杂度为O(n+k)，空间复杂度为O(k).因此这个计数排序不仅仅与要排序的数值多少有关系，还与其中最大数值大小有关系。
下面我们通过图形来对比三种排序程序的表现，分别取不同数量、不同最大输入数值的情况进行对比。
图1显示了对0到100范围内的整数(k=100)进行排序的结果，输入序列个数在20000到1000000之间。
图1
图2中对排序数值的大小范围进行了扩大为0到10000(k=10000)。
图2
最后，我们将k提高到1000000，对比结果如图3所示。
图3
我们可以看到计数排序明显比Java库中使用的算法更快速。或许简单的整数排序不会有多大用处，下面我们比较对整数元组进行排序的不同。
