JS实现的计数排序与基数排序算法示例

可能需要先说明一下，计数排序和基数排序都是针对整数排序的算法。

1. 计数排序

计数排序的基本思想是将每个元素出现的次数统计出来，并按顺序排列。计数排序不是基于元素比较的，而是建立在元素的值域范围较小的前提下的。因此，计数排序的时间复杂度是O(n+k)，其中k是元素的值域大小。

算法步骤

1. 统计每个数字出现的次数，得到一个长度为k的计数数组。
2. 将计数数组进行变形，使得第i个元素是所有小于等于i的元素出现次数的总和（从1开始累积），这样计数数组中的值就是元素排名。
3. 开一个长度为n的排序数组，遍历原数组，将每个元素插入到排序数组中对应的位置，再将计数数组中对应元素的值-1。

示例1

假设有一个需要排序的数组arr为[1, 3, 2, 3, 2, 4, 1, 5, 2]，值域为[1, 5]。

1. 初始化长度为5的计数数组count为[0, 0, 0, 0, 0]。
2. 遍历arr数组，对于每遇到一个数，则在count数组相应位置上加1。

遍历到1时，count数组变为 [1, 0, 0, 0, 0]
遍历到3时，count数组变为 [1, 0, 0, 1, 0]
遍历到2时，count数组变为 [1, 0, 1, 1, 0]
遍历到3时，count数组变为 [1, 0, 1, 2, 0]
遍历到2时，count数组变为 [1, 0, 2, 2, 0]
遍历到4时，count数组变为 [1, 0, 2, 2, 1]
遍历到1时，count数组变为 [2, 0, 2, 2, 1]
遍历到5时，count数组变为 [2, 0, 2, 2, 2]
遍历到2时，count数组变为 [2, 0, 3, 2, 2]

1. 对于计数数组count进行变形，累加每个位置前面的元素。在本例中，累加后的计数数组count变为[2, 2, 5, 7, 9]。
2. 创建一个长度为9的新数组sorted，遍历原始数组arr，将数字按照排名依次放入新数组中。

第一次取数字1，由于该数的排名为2，所以将该数放到sorted数组的索引为1的位置。
第二次取数字3，由于该数的排名为5，所以将该数放到sorted数组的索引为5的位置。
第三次取数字2，由于该数的排名为3，所以将该数放到sorted数组的索引为3的位置。
第四次取数字3，由于该数的排名为5，所以将该数放到sorted数组的索引为6的位置。 
第五次取数字2，由于该数的排名为3，所以将该数放到sorted数组的索引为4的位置。
第六次取数字4，由于该数的排名为7，所以将该数放到sorted数组的索引为7的位置。
第七次取数字1，由于该数的排名为2，所以将该数放到sorted数组的索引为2的位置。
第八次取数字5，由于该数的排名为9，所以将该数放到sorted数组的索引为9的位置。
第九次取数字2，由于该数的排名为3，所以将该数放到sorted数组的索引为5的位置。

排序后的数组为[1, 1, 2, 2, 2, 3, 3, 4, 5]。

示例2

function countingSort(arr) {
  let max = Math.max(...arr);
  let count = new Array(max + 1).fill(0);
  for (let num of arr) {
    count[num]++;
  }
  let sortedIndex = 0;
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      arr[sortedIndex++] = i;
      count[i]--;
    }
  }
  return arr;
}

该示例代码演示了计数排序的基本实现，时间复杂度为O(n+k)。函数接收一个数组参数arr，返回排好序的数组。对于每个数字num，遍历数组并将计数数组对应位置+1。然后根据计数数组，将所有数字放入排序数组中。函数内使用了一个while循环来处理数字重复的情况。

2. 基数排序

基数排序的基本思想是将整数按位数切割成不同的数字，然后按每个位数分别进行比较排序，最终实现全局排序。基数排序属于非比较排序算法，时间复杂度为O(dn)，其中d是数字位数。通常情况下，基数排序用于对整数进行排序。

算法步骤

1. 取得操作数的最大位数，假设是k位。
2. 对数组从最低位开始（第1位）进行排序。
3. 从最低位排到最高位。
4. 排序使用的方法：用10个桶依次分别对个位、十位、百位...进行排序。

示例1

假设有一个需要排序的数组arr为[3, 30, 34, 5, 9]。

1. 取得数组arr的位数的最大值max，max为2位。
2. 从低位到高位，分别按每一位进行排序。
3. 对于本例，首先按照个位排序，将每个数字放入桶中，按照桶的顺序将数字取出，并按照个位排序。排序后的数组为[30, 5, 9, 3, 34]。
4. 接下来按照十位排序，将每个数字放入桶中，按照桶的顺序取出数字，再按照个位排序。排序后的数组为[3, 30, 34, 5, 9]。
5. 排序完成，最终数组为[3, 30, 34, 5, 9]。

示例2

function radixSort(arr) {
  const max = Math.max(...arr);
  const maxDigit = String(max).length;
  let mod = 10;
  let dev = 1;
  for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    let bucketList = new Array(10).fill([]);
    for (let j = 0; j < arr.length; j++) {
      let num = parseInt(arr[j] % mod / dev);
      let bucket = bucketList[num];
      bucket.push(arr[j]);
      bucketList[num] = bucket;
    }
    let res = [];
    for (let j = 0; j < bucketList.length; j++) {
      res.push(...bucketList[j]);
    }
    arr = res;
  }
  return arr;
}

该示例代码演示了基数排序的基本实现，时间复杂度为O(dn)。函数接收一个数组参数arr，返回排好序的数组。函数内的dev和mod用来分别获取数字每一位数值，在每次排序的循环中创建一个长度为10的二维桶bucketList。对于每个数字num，首先计算其在当前位的值，然后将其放入对应的桶上。排序完成后，将bucketList中的数字依次放入一个新数组res中，返回res。