基数排序

基数排序是一种非比较型整数排序算法，其原理是将所有待比较数值 (正整数) 统一为同样的数位长度，数位较短的数前面补零。然后按每个位数分别比较，当所有位数比较完成后，数列就变成了一个有序序列。由于整数也可以表达字符串 (比如名字或日期) 和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序 VS 计数排序 VS 桶排序

这三种算法都利用了桶的概念，但对桶的使用上有明显差异：

• 基数排序：根据健值的每位数字来分桶；
• 计数排序：每个桶只存储单一健值；
• 桶排序：每个桶存储一定范围的数值；

两种排序方式

最低位优先法 LSD (Least significant digital)
LSD的排序方式从健值的最右边 (数值的最低位) 开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成后，数列就成了一个有序序列。

最高位优先法 MSD (Most Significant Digit first)
MSD的排序方式从健值的最左边 (数值的最高位) 开始，依次进行一次排序。

基本解法

第一步
**
以 LSD 为例，假设待排序的数列如下：

3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48

首先根据个位数 (数值的最低位) 的数值，在走访数值时将它们分别分配到编号 0 到 9 的桶子中：
第二步

接下来将这些桶中的数值重新串接起来 (先入桶的元素先出桶，也就是队列的先进先出原则)，成为以下的数列：

50, 2, 3, 44, 4, 5, 15, 36, 26, 46, 47, 27, 38, 48, 19

接着再进行一次分配，这次是根据十位数来分配：
第三步

接下来也是将这些桶中的数值重新串接起来 (先入桶的元素先出桶，也就是队列的先进先出原则)，成为以下的数列：

2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50

这个时候整个数列已经排序完毕。如果排序的数字有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD 的基数排序适用于位数较小的数列，如果位数多的话，使用 MSD 的效率会比较好。MSD 的方式与 LSD 相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个 “桶” 中建立 “子桶”，将每个桶中的数值按照下一数位的值分配到 “子桶” 中。在进行完最低位数的分配后再合并回单一的数组中。

动图演示

JavaScript 代码实现

=-// LSD Radix Sort
const counter = [];
function radixSort(arr, maxDigit) {
    let mod = 10;
  let dev = 1;
  for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
      for (let j = 0; j < arr.length; j++) {
        const bucket = parseInt((arr[j] % mod) / dev);
      if(counter[bucket] == null) {
         counter[bucket] = [];
      }
      counter[bucket].push(arr[j]);
    }
    let pos = 0;
    for (let j = 0; j < counter.length; j++) {
        let value = null;
      if (counter[j] != null) {
          while((value = counter[j].shift()) != null) {
          arr[pos++] = value;
        }
      }
    }
  }
  return arr;
}