排序算法10-基数排序

基数排序

• 平均时间复杂度:O(nk)
• 最好情况:O(nk)
• 最坏情况:O(nk)
• 空间复杂度:O(n+k)
• 排序方式:Out-place
• 稳定性:稳定

算法步骤:
1.将整数按位数切割成不同的数字，然后按每个位数分别比较
2.例如先按个位排序，然后按十位排序，由于此时个位是有序的所以先入列的肯定更小
3.继续依次比较更高位

function radixSort(arr) {
  //需要获取最大值的位数
  let counter = [];
  let maxValue = Math.max(...arr);
  let number = (maxValue + "").length;

  let mod = 10,
    dev = 1;
  for (let i = 0; i < number; i++, dev *= 10, mod *= 10) {
    for (let j = 0; j < arr.length; j++) {
      let bucket = parseInt((arr[j] % mod) / dev);
      if (!counter[bucket]) counter[bucket] = [];
      counter[bucket].push(arr[j]);
    }
    let pos = 0;
    for (let j = 0; j < counter.length; j++) {
      if (counter[j]) {
        while (counter[j].length) {
          arr[pos++] = counter[j].shift();
        }
      }
    }
  }
}