>[success] # 桶排序 [可视化桶排序算法](https://juejin.im/post/6844904195896639496) ~~~ 1.桶排序和计数排序很像，如果把计数排序每个数组对应位置看成桶，那么每个数据都有 一个属于自己的桶 2.桶排序：它利用函数的映射关系，将待排序元素分到有限的桶里，然后桶内元素再进行排序 （可能是别的排序算法），最后将各个桶内元素输出得到一个有序数列 ~~~ >[info] ## js 代码实现 ~~~ 1.首先我们需要桶，并且需要将这些元素分配到对应桶中，我们可以用二维数组的格式抽象化这种数据 结构'[ [ 5, 1 ], [ 10, 6, 7 ], [ 15 ], [ 19 ] ]',然后我们再把每个桶中的数据排序，最后就是整个数组的排序 ~~~ >[danger] ##### 代码实现 ~~~ 1.在整个过程中最重要的就是计算桶的个数，可以利用公式'数组最大值和最小值的差值并与桶的大小进行除法计算' 1.1.这句话意味着我们还要求出最大值和最小值（等价替换法） 1.2.我们还要做一个桶的计算"((最大值-最小值)/默认分组桶的个数)+1" 1.3.当然我们还要把一维数组的值对应放进二维数组的桶中，这些值具体属于哪个桶，就跟我们 在求出这些桶分组公式一样不过最大值变成了这些项 注：上面描述的步骤我们都放在一个叫'createBuckets' 方法中 2.注意了桶排序每个桶中具体顺序还是需要配合其他排序算法的 ~~~ ~~~ function bucketSort(array, bucketSize = 5) { if (array.length < 2) { return array; } const buckets = createBuckets(array, bucketSize); return sortBuckets(buckets); // 其他排序算法对每个桶中的内容排序 } function createBuckets(array,bucketSize){ // 求出最大值和最小值 let maxValue = array[0] let minValue = array[0] for(let i=0,item;item = array[i++];){ if(item>maxValue){ maxValue = item }else if(item<minValue){ minValue = item } } // 根据公式算出桶的个数 const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; // 将这些桶和数组进行规整成二维数组 const bukets = Array.from({length:bucketCount},(v,i)=>[]) // 将之前的数据放回到这些桶中 for(let i=0;item;item=array[i++]){ // 算出当前值应该属于哪个桶 const bucketIndex = Math.floor((array[i] - minValue) / bucketSize); // {8} buckets[bucketIndex].push(array[i]); } return buckets; } function sortBuckets(buckets) { const sortedArray = []; for (let i = 0; i < buckets.length; i++) { if (buckets[i] != null) { insertionSort(buckets[i]); // 这里采用了插入排序关于插入排序的写法参考插入排序代码 sortedArray.push(...buckets[i]); } } return sortedArray; } ~~~