1. 桶排序介绍
桶排序(Bucket sort)是一种基于计数的排序算法，工作的原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。当要被排序的数据内的数值是均匀分配的时候，桶排序时间复杂度为Θ(n)。桶排序不同于快速排序，并不是比较排序，不受到时间复杂度 O(nlogn) 下限的影响。
桶排序按下面4步进行：
（1）设置固定数量的空桶。
（2）把数据放到对应的桶中。
（3）对每个不为空的桶中数据进行排序。
（4）拼接从不为空的桶中数据，得到结果。
桶排序，主要适用于小范围整数数据，且独立均匀分布，可以计算的数据量很大，而且符合线性期望时间。
2. 桶排序算法演示
举例来说，现在有一组数据[7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]，怎么对其按从小到大顺序排序呢？
操作步骤说明：
（1）设置桶的数量为5个空桶，找到最大值110，最小值7，每个桶的范围20.8=(110-7+1)/5 。
（2）遍历原始数据，以链表结构，放到对应的桶中。数字7，桶索引值为0，计算公式为floor((7 – 7) / 20.8)， 数字36，桶索引值为1，计算公式floor((36 – 7) / 20.8)。
（3）当向同一个索引的桶，第二次插入数据时，判断桶中已存在的数字与新插入数字的大小，按照左到右，从小到大的顺序插入。如：索引为2的桶，在插入63时，桶中已存在4个数字56，59，60，65，则数字63，插入到65的左边。
（4）合并非空的桶，按从左到右的顺序合并0，1，2，3，4桶。
（5）得到桶排序的结构
3. Nodejs程序实现
像桶排序这种成熟的算法，自己实现一下并不难，按照上文的思路，我写了一个简单的程序实现。我感觉其中最麻烦的部分，是用Javascript操作链表。
现实代码如下：
'use strict'; ///////////////////////////////////////////////// // 桶排序 ///////////////////////////////////////////////// var _this = this , L = require('linklist');//链表 /** * 普通数组桶排序,同步 * * @param arr Array 整数数组 * @param num 桶的个数 * * @example: * sort([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1],5) * sort([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1],5,0,5) */ exports.sort = function (arr, count) { if (arr.length == 0) return []; count = count || (count > 1 ? count : 10); // 判断最大值、最小值 var min = arr[0], max = arr[0]; for (var i = 1; i < arr.length; i++) { min = min < arr[i] ? min : arr[i]; max = max > arr[i] ? max : arr[i]; } var delta = (max - min + 1) / count; // console.log(min+","+max+","+delta); //初始化桶 var buckets = []; //存储数据到桶 for (var i = 0; i < arr.length; i++) { var idx = Math.floor((arr[i] - min) / delta); // 桶索引 if (buckets[idx]) {//非空桶 var bucket = buckets[idx]; var insert = false;//插入标石 L.reTraversal(bucket, function (item, done) { if (arr[i] <= item.v) {//小于，左边插入 L.append(item, _val(arr[i])); insert = true; done();//退出遍历 } }); if (!insert) { //大于，右边插入 L.append(bucket, _val(arr[i])); } } else {//空桶 var bucket = L.init(); L.append(bucket, _val(arr[i])); buckets[idx] = bucket; //链表实现 } } var result = []; for (var i = 0, j = 0; i < count; i++) { L.reTraversal(buckets[i], function (item) { // console.log(i+":"+item.v); result[j++] = item.v; }); } return result; } //链表存储对象 function _val(v) { return {v: v} }
运行程序：
var algo = require('./index.js'); var data = [ 7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67,101 ]; console.log(data); console.log(algo.bucketsort.sort(data,5));//5个桶 console.log(algo.bucketsort.sort(data,10));//10个桶
输出：
[ 7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101 ] [ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ] [ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ]
需要说明的是：
（1）桶内排序，可以像程序中所描述的，在插入过程中实现；也可以插入不排序，在合并过程中，再进行排序，可以调用快度排序。
（2）链表，在Node的底层API中，有一个链表的实现,我没有直接使用，而是通过linklist包调用的:https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
4. 案例：桶排序统计高考分数
桶排序最出名的一个应用场景，就是统计高考的分数。一年的全国高考考生人数为900万人，分数使用标准分，最低200 ，最高900 ，没有小数，如果把这900万数字进行排序，应该如何做呢？
算法分析：
（1）如果使用基于比较的排序，快速排序，平均时间复杂度为O(nlogn) = O(9000000*log9000000)=144114616=1.44亿次比较。
（2）如果使用基于计数的排序，桶排序，平均的时候复杂度，可以控制在线性复杂度，当创建700桶时从200分到900分各一个桶，O(N)=O(9000000)，就相当于扫描一次900W条数据。
我们跑一个程序，对比一次快速排序和桶排序。