radix sorting

原创
2015/04/07 17:41
阅读数 35

radix sorting基于bucket sorting,先按照个位数排序,再按照十位数排序,再百位。。。

代码参考自 

http://en.wikipedia.org/wiki/Radix_sort

<script>

function printArr(arr)

{

console.log(arr);

}


function radixSort(arr)

{

var retval = [];

var maxNum = function(){

var tmp = 0;

var len = arr.length;

var i = 0;

while(i <= len)

{

if(tmp < arr[i])

{

tmp = arr[i]

}

++i;

}

return tmp;

}();

var base = 10;

var len = arr.length;

var buckets = [0, 0, 0, 0, 0, 0, 0, 0, 0];

arr.forEach(function(e){

retval.push(e);

});

var exp = 1; 

while(maxNum/exp > 0)

{

for(var i = 0; i < len; i++)

{  

 buckets[Math.floor(arr[i] / exp) % base]++;

}

for(i = 1; i < base; i++)

{

buckets[i] += buckets[i - 1];

}

for(i = len - 1; i >= 0; i--)

{

retval[--buckets[Math.floor(arr[i] / exp) % base]] = arr[i];

}

arr.length = 0;

retval.forEach(function(e){

arr.push(e);

});

exp *= base;

for(i = 0; i < base; i++)

{

buckets[i] = 0;

}

//printArr(retval);

}

return retval;

}


var datas = [100, 31, 52, 208, 191, 321, 88, 910, 301, 2, 55, 101, 233, 512];


printArr(datas);


var output = radixSort(datas);


printArr(output);

</script>


展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部