基数排序（radix sort）属于“分配式排序”（distribution sort），它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
先看一下基数排序的的实现步骤（以两位数为例），需要扫描两次，第一次按个位数字进行排序，第二次按十位数字排序，每个数字根据对应的数值分配到到不同的盒子里，最后将盒子的数字依次取出，组成新的列表即为排序好的数字。
假设我们有一串数字，分别为 73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数字排序，放到不同的盒子里，如下图
第一次排序
接下来将这些盒子中的数值重新串接起来，成为以下的数列：81, 22, 73, 93, 43, 14, 55, 65, 28, 39
然后根据十位数字排序，再放到不同的盒子里，如下图
第二次排序
接下来将这些盒子中的数值重新串接起来，整个数列已经排序完毕：14, 22, 28, 39, 43, 55, 65, 73, 81, 93
我们已经了解了基数排序的算法思想，接着我们要结合队列去实现它，一起来看看吧。
//基数排序 var queues = []; //定义队列数组 var nums = []; //定义数字数组 //选十个0~99的随机数进行排序 for ( var i = 0 ; i < 10 ; i ++ ){ queues[i] = new Queue(); nums[i] = Math.floor( Math.random() * 101 ); } //排序之前 console.log( 'before radix sort: ' + nums ); //基数排序 distribution( nums , queues , 10 , 1 ); collect( queues , nums ); distribution( nums , queues , 10 , 10 ); collect( queues , nums ); //排序之后 console.info('after radix sort: ' + nums ); //根据相应的（个位和十位）数值，将数字分配到相应队列 function distribution ( nums , queues , n , digit ) { //digit表示个位或者十位的值 for( var i = 0 ; i < n ; i++ ){ if( digit == 1){ queues[ nums[i] % 10 ].enqueue( nums[i] ); }else{ queues[ Math.floor( nums[i] / 10 ) ].enqueue( nums[i] ); } } } //从队列中收集数字 function collect ( queues , nums ) { var i = 0; for ( var digit = 0 ; digit < 10 ; digit ++ ){ while ( !queues[digit].empty() ){ nums[ i++ ] = queues[digit].front(); queues[digit].dequeue(); } } }
我这里贴出两组测试的结果，大家自己动手实践一下。
//第一组测试 before radix sort: 23,39,2,67,90,41,47,21,98,13 after radix sort: 2,13,21,23,39,41,47,67,90,98 //第二组测试 before radix sort: 29,62,38,16,55,26,33,54,76,65 after radix sort: 16,26,29,33,38,54,55,62,65,76
至此，我们队列也就告一段落了，大家还可以往深入拓展，比如优先队列，循环队列等，希望大家能发散思维，多动手实践，一起加油！
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：测试上述代码运行效果。
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
您可能感兴趣的文章: