基数排序
louzhedong opened this issue · 0 comments
louzhedong commented
算法名称
基数排序
实现思路
- 是桶排序的一个拓展
- 将数字统一为同样的数位长度,数位较短的数前面补零
- 从低位开始,进行比较,对数组排序,逐步排到高位
- 排完最高位后,就是一个有序数组
算法分析
时间复杂度根据不同数据大小有所不同,当最大的数字较小时,时间复杂度是O(N),当最大的数字较大时,时间复杂度是O(N*logN)
算法实现
function RadixSort(array) {
var max = Number.MIN_VALUE,
length = array.length;
for (var i = 0; i < length; i++) {
if (array[i] > max) {
max = array[i];
}
}
var numberLength = max.toString().length;
for (var i = 0; i < length; i++) {
var current = array[i].toString();
var currentLength = current.length;
for (var j = 0; j < numberLength - currentLength; j++) {
current = "0" + current;
}
array[i] = current;
}
// 从个位开始往前排
for (var i = numberLength - 1; i >= 0; i--) {
for (var j = 1; j < length; j++) {
var temp = array[j];
var k = j - 1;
for (; k >= 0; k--) {
if (temp[i] < array[k][i]) {
array[k + 1] = array[k];
} else {
break;
}
}
array[k + 1] = temp;
}
}
for (var i = 0; i < length; i++) {
array[i] = parseInt(array[i]);
}
}