问答题5题:请手写“基数排序”

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

参考答案:

算法简介

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

算法描述

具体算法描述如下:

  • 取得数组中的最大数,并取得位数;
  • arr为原始数组,从最低位开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

代码实现

1/** 2 * 基数排序适用于: 3 * (1)数据范围较小,建议在小于1000 4 * (2)每个数值都要大于等于0 5 * @author damonare 6 * @param arr 待排序数组 7 * @param maxDigit 最大位数 8 */ 9//LSD Radix Sort 10 11function radixSort(arr, maxDigit) { 12 var mod = 10; 13 var dev = 1; 14 var counter = []; 15 console.time('基数排序耗时'); 16 for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { 17 for(var j = 0; j < arr.length; j++) { 18 var bucket = parseInt((arr[j] % mod) / dev); 19 if(counter[bucket]== null) { 20 counter[bucket] = []; 21 } 22 counter[bucket].push(arr[j]); 23 } 24 var pos = 0; 25 for(var j = 0; j < counter.length; j++) { 26 var value = null; 27 if(counter[j]!=null) { 28 while ((value = counter[j].shift()) != null) { 29 arr[pos++] = value; 30 } 31 } 32 } 33 } 34 console.timeEnd('基数排序耗时'); 35 return arr; 36} 37var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]; 38console.log(radixSort(arr,2)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] 39

算法分析

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

小程序刷题更方便

预览

关注公众号获取最新面经

预览

加面试交流群

赞赏支持

预览

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