桶排序：
方法一：每个桶只放相同的数字
入桶过程：1、 把正数和0存入正数桶，把负数存入负数桶；2、 把数组中的每项作为正数桶或负数桶的下标存入到对应的key里； 出桶过程：
先遍历正数桶或负数桶，因为桶里每项都是数组，在遍历每项function bucketSort(array){ var bucket = [], //正数桶 negativeBucket = [], //负数桶 result = [], //最终结果 abs, //负数的绝对值 k //存储正数桶或负数桶每项的length //入桶 for(var i = 0; i < array.length; i++){ if(array[i] < 0){ abs = Math.abs(array[i]) if(!negativeBucket[abs]){ negativeBucket[abs] = [] } negativeBucket[abs].push(array[i]) }else{ if(!bucket[array[i]]){ bucket[array[i]] = [] } bucket[array[i]].push(array[i]) } } //出桶 var l = negativeBucket.length for(var i = l - 1; i >= 0; i --){ //遍历负数桶，和正数桶正好相反 if(negativeBucket[i]){ k = negativeBucket[i].length for(var j = 0; j < k; j++){ result.push(negativeBucket[i][j]) } } } for(var i = 0; i < bucket.length; i++){ //遍历正数桶 if(bucket[i]){ k = bucket[i].length for(var j = 0; j < k; j++){ result.push(bucket[i][j]) } } } return result}var a = [1,23,5,6,7,-6,-9,-11,0,-1,-55,-4,7,4,1,222,3,7]bucketSort(a) 方法二：每个桶放一个范围的数
function bucketSort(array, step) { var result = [], //存储最终结果 bucket = [], //要用到的桶的数组 bucketCount, //桶的数量 l = array.length, i, j, k, s, max = array[0],//最大数 min = array[0],//最小数 temp; //找出 array 中最大数和最小数 for (i = 1; i < l; i++) { if (array[i] > max) { max = array[i] } if (array[i] < min) { min = array[i]; } } min = min - 1; //如果 array 中有 4 个数，定义每个桶放 2 个数，那只要 2 个桶就够了，最后结果会少一个数，最小数上 -1，需要的桶就会变成 3 个 bucketCount = Math.ceil((max - min) / step); // 需要桶的数量，和 bucket.length相等 console.log(bucketCount) for (i = 0; i < l; i++) { temp = array[i]; for (j = 0; j < bucketCount; j++) { if (temp > (min + step * j) && temp <= (min + step * (j + 1))) { // 判断放入哪个桶 /* | j | min + step * j | min + step * (j + 1) | | 0 | -2 | 0 | | 1 | 0 | 2 | | 2 | 2 | 4 | temp 取值 3,-1,0 j 取值 0,1,2 当 i = 0 时,temp = 3,只有 j = 2 能进来; 当 i = 1 时,temp = -1,只有 j = 0 能进来; 当 i = 2 时,temp = 0,只有 j = 0 能进来 */ //bucket 是桶的数组，把每个桶变成数组 //这里 j 的取值顺序是 2、1、0，取到的值是 2、0、0 if (!bucket[j]) { bucket[j] = []; } // 通过插入排序将数字插入到桶中的合适位置 s = bucket[j].length; //前两次 s 是 0，第三次 s 为 1 if (s > 0) { //第三次走这边 for (k = s - 1; k >= 0; k--) { if (bucket[j][k] > temp) { bucket[j][k + 1] = bucket[j][k]; } else { break; } } bucket[j][k + 1] = temp; //这里 j 取值 0，也就是说放入第一个桶，k + 1 往后放 }else if(s <= 0) { //前两次走这边 bucket 中 key 为 0,2有值了 bucket[j].push(temp); } } } } for (i = 0; i < bucketCount; i++) { // 循环取出桶中数据 if (bucket[i]) { k = bucket[i].length; for (j = 0; j < k; j++) { result.push(bucket[i][j]); } } } return result; } var a = [-3,-1,0] bucketSort(a) 基数排序
排序过程：准备 0-9 号十个桶
第一次循环：入桶：按个位数排序，依次放入0-9号桶内出桶：从 0 号桶依次开始，按先入先出的方式出桶第二次循环入桶：按十位数排序，依次放入0-9号桶内，位数不够的补 0出桶：从 0 号桶依次开始，按先入先出的方式出桶第三次按百位排序... 第四次按千位排序...直到全部排完function radixSort(array){ var bucket = [], i, max = array[0]; for(i = 1; i < array.length; i++){ if(array[i] > max){ max = array[i] } } for(i = 0; i < 10; i++){ bucket[i] = [] } var loop = (max + '').length for(i = 0; i < loop; i++){ for(j = 0; j < array.length;j++){ var str = array[j] + '' if(str.length >= i + 1){ var k = str[str.length - i - 1] //找出对应位数，比如 345 这个数，第1次找出个位 5，第2次找出十位数 4，第3次找出百位数 3 bucket[k].push(array[j]) }else{ bucket[0].push(array[j]) } } array.splice(0,array.length) //清空数组 for(j = 0; j < 10; j++){ var t = bucket[j].length for(var g = 0; g < t; g++){ array.push(bucket[j][g]) } bucket[j] = [] //清空桶 } } return array}a=[22,3,33,2,1,777]radixSort(a)