问答题6题:请手写“桶排序”

难度:
更新时间:2021-07-18

参考答案:

算法简介

桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

算法描述

具体算法描述如下:

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。

代码实现

1/*方法说明:桶排序 2@param array 数组 3@param num 桶的数量*/ 4function bucketSort(array, num) { 5 if (array.length <= 1) { 6 return array; 7 } 8 var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0; 9 num = num || ((num > 1 && regex.test(num)) ? num : 10); 10 console.time('桶排序耗时'); 11 for (var i = 1; i < len; i++) { 12 min = min <= array[i] ? min : array[i]; 13 max = max >= array[i] ? max : array[i]; 14 } 15 space = (max - min + 1) / num; 16 for (var j = 0; j < len; j++) { 17 var index = Math.floor((array[j] - min) / space); 18 if (buckets[index]) { // 非空桶,插入排序 19 var k = buckets[index].length - 1; 20 while (k >= 0 && buckets[index][k] > array[j]) { 21 buckets[index][k + 1] = buckets[index][k]; 22 k--; 23 } 24 buckets[index][k + 1] = array[j]; 25 } else { //空桶,初始化 26 buckets[index] = []; 27 buckets[index].push(array[j]); 28 } 29 } 30 while (n < num) { 31 result = result.concat(buckets[n]); 32 n++; 33 } 34 console.timeEnd('桶排序耗时'); 35 return result; 36} 37var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; 38console.log(bucketSort(arr,4));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

算法分析

桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。

  • 最佳情况:T(n) = O(n+k)
  • 最差情况:T(n) = O(n+k)
  • 平均情况:T(n) = O(n2)
预览

小程序刷题更方便

预览

关注公众号获取最新面经

预览

加面试交流群

赞赏支持

预览

题库维护不易,您的支持就是我们最大的动力!