桶排序：
方法一：每个桶只放相同的数字
入桶过程：
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)
