基数排序

[louzhedong]

算法名称

基数排序

实现思路

• 是桶排序的一个拓展
• 将数字统一为同样的数位长度，数位较短的数前面补零
• 从低位开始，进行比较，对数组排序，逐步排到高位
• 排完最高位后，就是一个有序数组

算法分析

时间复杂度根据不同数据大小有所不同，当最大的数字较小时，时间复杂度是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]);
  }
}