摘要：桶排序可以说得上是最简单的排序算法了，但是它的使用范围非常狭窄，不过不可否认的是在其适用范围内，它的性能要比快速排序还要快上很多倍。
桶排序可以说得上是最简单的排序算法了，但是它的使用范围非常狭窄，不过不可否认的是在其适用范围内，它的性能要比快速排序还要快上很多倍。
没错，桶排序也是一种非比较型排序算法，这也正是它能够超越快速排序的原因。
桶排序主要有以下缺陷：
参与排序的数组存放的必须是整数。
数组中的最大数和最小数保持在一个合理的间距内。
《PHP程序设计》第二版下载本书图文并茂，详细讲解了使用LAMP（PHP）脚本语言开发动态Web程序的方法，如架设WAMP平台，安装与配置开源Moodle平台，PHP程序设计技术，开发用户注册与验证模块，架设LAMP平台。 本书适合计算机及其相关专业本、专科学生作为学习LAMP（PHP）程序设计或动态Web编程的教材使用，也适合对动态Web编程感兴趣的读者自觉使用，对LAMP（PHP）程序设计人员也具有一定的参考价值。
需要额外的内存空间。
下面将通过一个例子讲解桶排序的核心思想：
假如说我们需要对全国高考语文成绩进行排序，由于总分只有 150 分，而且所有的值都在 [0, 150] 之间，所以我们可以申请一个大小为 151 的辅助数组。
|
1 2 3 4 5 |
var countArray = []; for(var i = 0; i 150; i++) { countArray[i] = 0; }
|
首先我们将数组的值都置为 0。然后我们以各考生的成绩为下标递增辅助数组的值。比如说一个考生成绩为 90，那么我们就让 countArray[90]++，这样一直运算下去，直到所有的考生成绩都被遍历完，我们就可以统计出来每个分数有多少考生，然后再将辅助数组中的值复制回原数组，整个数组自然而然就有序了！
实现
大概了解了桶排序的思想，下面就来实现一下，假说某年参加高考的学生共有 500 万人，我们对其语文成绩进行排序。
下面是排序代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
function countSort(array, k) { var length = array.length, countArray = [], i;
for (i = 0; i k; i++) { countArray[i] = 0; }
for (i = 0; i length; i++) { countArray[array[i]]++; }
var z = 0; for (i = 0; i k; i++) { while (countArray[i]-- > 0) { array[z++] = i; } } }
|
下面是测试代码：
|
1 2 3 4 5 6 7 8 9 10 11 |
var array = [];
for(var i = 0; i 5000000; i++) { array.push(Math.floor(Math.random() * 151)); }
console.time(); countSort(array,151); console.timeEnd(); console.log(array);
|
以上代码在我电脑上的运行时间在 23ms 左右，可见，桶排序排序 500万数据的速度是如此之快，而我用快速排序对同一个数组进行排序，花了 320 ms 左右。
所以，如果在合适的时机选择计数排序，将节省很多时间。
改进
看了以上代码也许你发现了，上述代码如果排序一个数值在 [10000, 10200] 范围内的数组的话，将申请大量的内存，为了节省内存，我们不得不改进这个算法，让其适应指定范围内排序。
很简单的，我们可以在方法中设置一个 low 和 max 参数，就可以灵活自如了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
function countSort(array, low, max) { var length = array.length, countArray = [], i, k = max - low + 1;
for (i = 0; i k; i++) { countArray[i] = 0; }
for (i = 0; i length; i++) { countArray[array[i] - low]++; }
var z = 0; for (i = 0; i k; i++) { while (countArray[i]-- > 0) { array[z++] = i + low; } }
console.log(countArray.length); }
|
总结
最近一直在学习排序算法，发现比较型算法虽然速度比较慢一些(比较型算法的下限是 O(NlogN))，但是适用范围很广。非比较型算法虽然使用范围很有限，但是其速度非常之快。所以在选择排序算法时，根据程序的数值类型以及范围，首先要考虑是否能够使用非比较型算法，如果不可以再选用比较型算法，比如快速排序。
