桶排序详解

桶排序其实是对计数排序的优化版本，桶排序是每个桶存储一定范围的元素，通过映射函数将待排序的数组中的元素映射到对应的桶中，对每个桶再进行排序，将桶中的数据重新逐个放回的原数组中。

1.算法步骤

• 确定排序桶的个数，找出数组中最大最小值，划分每个桶的范围。
• 通过映射函数把数组中的元素全部映射到对应的桶中。
• 对每个桶进行排序（根据自己喜爱，选择不同的排序方式）
• 把桶中的元素逐个放回原数组中。

2.算法演示流程

3.算法代码

function (arr, bucketNum){

        // 取最大值和最新值
                var maxValue = arr[0];
                var minValue = arr[0];

                for(var i = 0; i < arr.length - 1; i++){
                    if (maxValue < arr[i]) {
                        maxValue = arr[i];
                    }

                    if (minValue > arr[i]) {
                        minValue = arr[i];
                    }
                }

                // 创建桶，并把数据放在桶中
                var bucketArr = new Array(bucketNum);
                for(var j= 0; j < bucketNum; j++){
                    bucketArr[j] = [];
                }

                for(var k=0; k<arr.length; k++){
                    bucketArr[Math.floor((arr[k] - minValue) / bucketNum)].push(arr[k]);
                }

                arr.length = 0;
                for(var h=0; h<bucketNum; h++){
                    // 根据自己喜好，选在不同的排序方法
                    var sortArr = insertSort(bucketArr[h]);   // 选择之前的插入排序
                    for(var l=0; l<bucketArr[h].length; l++){
                        arr.push[sortArr[l]]
                    }

                }
                return arr;
            }