0323.md

基数排序

使用十个桶 0-9，把每个数从低位到高位根据位数放到相应的桶里，以此循环最大值的位数次。 ** 但只能排列正整数，因为遇到负号和小数点无法进行比较。 **

• 最好： O(n * k)，k表示最大值的位数。
• 最坏： O(n * k)
• 平均： O(n * k)

function radixSort(nums) {
  if (!Array.isArray(nums)) {
    return new TypeError('not a array');
  }
  if (nums.length < 2) {
    return nums;
  }
  // 计算位数
  function getDigits(n) {
    let sum = 0;
    while (n) {
      sum++;
      n = parseInt(n / 10);
    }
    return sum;
  }
  // 第一维表示位数即0-9，第二维表示里面存放的值
  let array = Array.from(Array(10).map(() => Array()));
  let max = Math.max(...nums);
  let maxDigits = getDigits(max);
  let len = nums.length;
  for (let i = 0; i < len; i++) {
    // 用0把每一个数都填充成相同的位数
    nums[i] = (nums[i] + '').padStart(maxDigits, 0);
    // 先根据个位数把每一个数放到相应的桶里
    let temp = nums[i][nums[i].length - 1];
    array[temp].push(nums[i]);
  }
  // 循环判断每个位数
  for (let i = maxDigits - 2; i >= 0; i--) {
    // 循环每一个桶
    for (let j = 0; j <= 9; j++) {
      let temp = array[j];
      let len = temp.length;
      // 根据当前的位数i把桶里的数放到相应的桶里
      while (len--) {
        let str = temp[0];
        temp.shift();
        array[str[i].push(str)];
      }
    }
  }
  // 修改回原数组
  let res = [].concat.apply([], array);
  nums.forEach((val, index) => {
    nums[index] = +res[index];
  });
}