4.5.1 线性时间的排序
哇，什么样的排序算法可以这么厉害？
让我们先来回顾一下以前所学的排序算法，无论是冒泡排序，还是快速排序，都是基于元素之间的比较 来进行排序的。
例如冒泡排序。
如下图所示，因为8>3，所以8和3的位置交换。
例如堆排序。
如下图所示，因为10>7，所以10和7的位置交换。
排序当然要先比较呀，难道还有不需要比较的排序算法？
有一些特殊的排序并不基于元素比较，如计数排序、桶排序、基数排序 。
以计数排序来说，这种排序算法是利用数组下标来确定元素的正确位置的。
4.5.2 初识计数排序
还是不明白，元素下标怎么能用来帮助排序呢？
那让我们来看一个例子。
假设数组中有20个随机整数，取值范围为0～10，要求用最快的速度把这20个整数从小到大进行排序。
如何给这些无序的随机整数进行排序呢？
考虑到这些整数只能够在0、1、2、3、4、5、6、7、8、9、10这11个数中取值，取值范围有限。所以，可以根据这有限的范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0。
假设20个随机整数的值如下所示。
9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9
下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加1操作。
例如第1个整数是9，那么数组下标为9的元素加1。
第2个整数是3，那么数组下标为3的元素加1。
继续遍历数列并修改数组……
最终，当数列遍历完毕时，数组的状态如下。
该数组中每一个下标位置的值代表数列中对应整数出现的次数。
有了这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。
0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10
显然，现在输出的数列已经是有序的了。
这就是计数排序的基本过程，它适用于一定范围内的整数排序。在取值范围不是很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn)的排序。
明白了，计数排序还真是个神奇的算法！那么，用代码怎么实现呢？
我写了一个计数排序的初步实现代码，我们来看一下。
1. public static int[] countSort(int[] array) {
2. //1.得到数列的最大值
3. int max = array[0];
4. for(int i=1; i
5. if(array[i] > max){
6. max = array[i];
7. }
8. }
9. //2.根据数列最大值确定统计数组的长度
10. int[] countArray = new int[max+1];
11. //3.遍历数列，填充统计数组
12. for(int i=0; i
13. countArray[array[i]]++;
14. }
15. //4.遍历统计数组，输出结果
16. int index = 0;
17. int[] sortedArray = new int[array.length];
18. for(int i=0; i
19. for(int j=0; j
20. sortedArray[index++] = i;
21. }
22. }
23. return sortedArray;
24. }
25.
26.
27. public static void main(String[] args) {
28. int[] array = new int[] {4,4,6,5,3,2,8,1,7,5,6,0,10};
29. int[] sortedArray = countSort(array);
30. System.out.println(Arrays.toString(sortedArray));
31. }
这段代码在开头有一个步骤，就是求数列的最大整数值max。后面创建的统计数组countArray，长度是max+1，以此来保证数组的最后一个下标是max。
4.5.3 计数排序的优化
从实现功能的角度来看，这段代码可以实现整数的排序。但是这段代码也存在一些问题，你发现了吗？
哦，让我想想……
对了！我们只以数列的最大值来决定统计数组的长度，其实并不严谨。例如下面的数列。
95，94，91，98，99，90，99，93，91，92
这个数列的最大值是99，但最小的整数是90。如果创建长度为100的数组，那么前面从0到89的空间位置就都浪费了！
怎么解决这个问题呢？
很简单，只要不再以输入数列的最大值+1 作为统计数组的长度，而是以数列最大值-最小值+1 作为统计数组的长度即可。
同时，数列的最小值作为一个偏移量，用于计算整数在统计数组中的下标。
以刚才的数列为例，统计出数组的长度为99-90+1=10，偏移量等于数列的最小值90。
对于第1个整数95，对应的统计数组下标是95-90 = 5，如图所示。
是的，这确实对计数排序进行了优化。此外，朴素版的计数排序只是简单地按照统计数组的下标输出元素值，并没有真正给原始数列进行排序。
如果只是单纯地给整数排序，这样做并没有问题。但如果在现实业务里，例如给学生的考试分数进行排序，遇到相同的分数就会分不清谁是谁。
什么意思呢？让我们看看下面的例子。
给出一个学生成绩表，要求按成绩从低到高进行排序，如果成绩相同，则遵循原表固有顺序。
那么，当我们填充统计数组以后，只知道有两个成绩并列为95分的同学，却不知道哪一个是小红，哪一个是小绿。
明白你的例子了，但为什么我的成绩最低呀……那么，这种分数相同的情况要怎么解决？
在这种情况下，需要稍微改变之前的逻辑，在填充完统计数组以后，对统计数组做一下变形。
仍然以刚才的学生成绩表为例，将之前的统计数组变形成下面的样子。
这是如何变形的呢？其实就是从统计数组的第2个元素开始，每一个元素都加上前面所有元素之和。
为什么要相加呢？初次接触的读者可能会觉得莫名其妙。
这样相加的目的，是让统计数组存储的元素值，等于相应整数的最终排序位置的序号。例如下标是9的元素值为5，代表原始数列的整数9，最终的排序在第5位。
接下来，创建输出数组sortedArray，长度和输入数列一致。然后从后向前遍历输入数列。
第1步，遍历成绩表最后一行的小绿同学的成绩。
小绿的成绩是95分，找到countArray下标是5的元素，值是4，代表小绿的成绩排名位置在第4位。
同时，给countArray下标是5的元素值减1，从4变成3，代表下次再遇到95分的成绩时，最终排名是第3。
第2步，遍历成绩表倒数第2行的小白同学的成绩。
小白的成绩是94分，找到countArray下标是4的元素，值是2，代表小白的成绩排名位置在第2位。
同时，给countArray下标是4的元素值减1，从2变成1，代表下次再遇到94分的成绩时（实际上已经遇不到了），最终排名是第1。
第3步，遍历成绩表倒数第3行的小红同学的成绩。
小红的成绩是95分，找到countArray下标是5的元素，值是3（最初是4，减1变成了3），代表小红的成绩排名位置在第3位。
同时，给countArray下标是5的元素值减1，从3变成2，代表下次再遇到95分的成绩时（实际上已经遇不到了），最终排名是第2。
这样一来，同样是95分的小红和小绿就能够清楚地排出顺序了，也正因为此，优化版本的计数排序属于稳定排序 。
后面的遍历过程以此类推，这里就不再详细描述了。
还真是够绕的，不过大体上明白了。那么，优化之后的计数排序如何用代码实现呢？
说起来复杂，其实代码很简洁，让我们来看一看。
1. public static int[] countSort(int[] array) {
2. //1.得到数列的最大值和最小值，并算出差值d
3. int max = array[0];
4. int min = array[0];
5. for(int i=1; i
6. if(array[i] > max) {
7. max = array[i];
8. }
9. if(array[i] < min) {
10. min = array[i];
11. }
12. }
13. int d = max - min;
14. //2.创建统计数组并统计对应元素的个数
15. int[] countArray = new int[d+1];
16. for(int i=0; i
17. countArray[array[i]-min]++;
18. }
19.
20. //3.统计数组做变形，后面的元素等于前面的元素之和
21. for(int i=1;i
22.
23. countArray[i] += countArray[i-1];
24. }
25. //4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
26. int[] sortedArray = new int[array.length];
27. for(int i=array.length-1;i>=0;i--) {
28. sortedArray[countArray[array[i]-min]-1]=array[i];
29. countArray[array[i]-min]--;
30. }
31. return sortedArray;
32. }
33.
34. public static void main(String[] args) {
35. int[] array = new int[] {95,94,91,98,99,90,99,93,91,92};
36. int[] sortedArray = countSort(array);
37. System.out.println(Arrays.toString(sortedArray));
38. }
小灰，如果原始数列的规模是n，最大和最小整数的差值是m，你说说计数排序的时间复杂度和空间复杂度是多少？
代码第1、2、4步都涉及遍历原始数列，运算量都是n，第3步遍历统计数列，运算量是m，所以总体运算量是3n+m，去掉系数，时间复杂度是O(n+m)。
至于空间复杂度，如果不考虑结果数组，只考虑统计数组大小的话，空间复杂度是O(m)。
不错哦，回答得很赞！
不过我有一点不太明白，既然计数排序这么强大，为什么很少被大家使用呢？
因为计数排序有它的局限性，主要表现为如下两点。
1. 当数列最大和最小值差距过大时，并不适合用计数排序。
例如给出20个随机整数，范围在0到1亿之间，这时如果使用计数排序，需要创建长度为1亿的数组。不但严重浪费空间，而且时间复杂度也会随之升高。
2. 当数列元素不是整数时，也不适合用计数排序。
如果数列中的元素都是小数，如25.213，或0.00 000 001这样的数字，则无法创建对应的统计数组。这样显然无法进行计数排序。
对于这些局限性，另一种线性时间排序算法做出了弥补，这种排序算法叫作桶排序 。
4.5.4 什么是桶排序
桶排序？那又是什么鬼？
桶排序同样是一种线性时间的排序算法。类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。
那么，桶排序中所谓的“桶”，又是什么呢？
每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。
假设有一个非整数数列如下：
4.5，0.84，3.25，2.18，0.5
让我们来看看桶排序的工作原理。
桶排序的第1步，就是创建这些桶，并确定每一个桶的区间范围。
具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定。
区间跨度 = （最大值-最小值）/ （桶的数量 - 1）
第2步，遍历原始数列，把元素对号入座放入各个桶中。
第3步，对每个桶内部的元素分别进行排序（显然，只有第1个桶需要排序）。
第4步，遍历所有的桶，输出所有元素。
0.5，0.84，2.18，3.25，4.5
到此为止，排序结束。
大体明白了，那么，代码怎么写呢？
我们来看一看桶排序的代码实现。
1. public static double[] bucketSort(double[] array){
2.
3. //1.得到数列的最大值和最小值，并算出差值d
4. double max = array[0];
5. double min = array[0];
6. for(int i=1; i
7. if(array[i] > max) {
8. max = array[i];
9. }
10. if(array[i] < min) {
11. min = array[i];
12. }
13. }
14. double d = max - min;
15.
16. //2.初始化桶
17. int bucketNum = array.length;
18. ArrayList
19. for(int i = 0; i < bucketNum; i++){
20. bucketList.add(new LinkedList
21. }
22.
23. //3.遍历原始数组，将每个元素放入桶中
24. for(int i = 0; i < array.length; i++){
25. int num = (int)((array[i] - min) * (bucketNum-1) / d);
26. bucketList.get(num).add(array[i]);
27. }
28.
29. //4.对每个桶内部进行排序
30. for(int i = 0; i < bucketList.size(); i++){
31. //JDK 底层采用了归并排序或归并的优化版本
32. Collections.sort(bucketList.get(i));
33. }
34.
35. //5.输出全部元素
36. double[] sortedArray = new double[array.length];
37. int index = 0;
38. for(LinkedList
39. for(double element : list){
40. sortedArray[index] = element;
41. index++;
42. }
43. }
44. return sortedArray;
45. }
46.
47. public static void main(String[] args) {
48. double[] array = new double[]
{4.12,6.421,0.0023,3.0,2.123,8.122,4.12, 10.09};
49. double[] sortedArray = bucketSort(array);
50. System.out.println(Arrays.toString(sortedArray));
51. }
在上述代码中，所有的桶都保存在ArrayList集合中，每一个桶都被定义成一个链表（LinkedList
同时，上述代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，各位读者可以简单地把它们当作一种时间复杂度为O(nlogn)的排序。
那么，桶排序的时间复杂度是多少呢？
桶排序的时间复杂度有些复杂，让我们来计算一下。
假设原始数列有n个元素，分成n个桶。
下面逐步来分析一下算法复杂度。
第1步，求数列最大、最小值，运算量为n。
第2步，创建空桶，运算量为n。
第3步，把原始数列的元素分配到各个桶中，运算量为n。
第4步，在每个桶内部做排序，在元素分布相对均匀的情况下，所有桶的运算量之和为n。
第5步，输出排序数列，运算量为n。
因此，桶排序的总体时间复杂度为O(n)。
至于空间复杂度就很容易得到了，同样是O(n)。
桶排序的性能并非绝对稳定。如果元素的分布极不均衡，在极端情况下，第一个桶中有n-1个元素，最后一个桶中有1个元素。此时的时间复杂度将退化为O(nlogn)，而且还白白创建了许多空桶。
由此可见，并没有绝对好的算法，也没有绝对不好的算法，关键要看具体的场景。
关于计数排序和桶排序的知识，我们就介绍到这里，下一章再见！