基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

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

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

2. 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

3. 算法步骤

  1. 取得数组中的最大数，并取得位数；
  2. arr为原始数组，从最低位开始取每个位组成radix数组；
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

4. LSD 基数排序动图演示

动图演示

5. 代码实现

1. JavaScript 代码实现

  1. //LSD Radix Sort
  2. var counter = [];
  3. function radixSort(arr, maxDigit) {
  4.     var mod = 10;
  5.     var dev = 1;
  6.     for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
  7.         for(var j = 0; j < arr.length; j++) {
  8.             var bucket = parseInt((arr[j] % mod) / dev);
  9.             if(counter[bucket]==null) {
  10.                 counter[bucket] = [];
  11.             }
  12.             counter[bucket].push(arr[j]);
  13.         }
  14.         var pos = 0;
  15.         for(var j = 0; j < counter.length; j++) {
  16.             var value = null;
  17.             if(counter[j]!=null) {
  18.                 while ((value = counter[j].shift()) != null) {
  19.                       arr[pos++] = value;
  20.                 }
  21.           }
  22.         }
  23.     }
  24.     return arr;
  25. }

2. Java 代码实现

  1. /**
  2.  * 基数排序
  3.  * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
  4.  */
  5. public class RadixSort implements IArraySort {
  7.     @Override
  8.     public int[] sort(int[] sourceArray) throws Exception {
  9.         // 对 arr 进行拷贝，不改变参数内容
  10.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  12.         int maxDigit = getMaxDigit(arr);
  13.         return radixSort(arr, maxDigit);
  14.     }
  16.     /**
  17.      * 获取最高位数
  18.      */
  19.     private int getMaxDigit(int[] arr) {
  20.         int maxValue = getMaxValue(arr);
  21.         return getNumLenght(maxValue);
  22.     }
  24.     private int getMaxValue(int[] arr) {
  25.         int maxValue = arr[0];
  26.         for (int value : arr) {
  27.             if (maxValue < value) {
  28.                 maxValue = value;
  29.             }
  30.         }
  31.         return maxValue;
  32.     }
  34.     protected int getNumLenght(long num) {
  35.         if (num == 0) {
  36.             return 1;
  37.         }
  38.         int lenght = 0;
  39.         for (long temp = num; temp != 0; temp /= 10) {
  40.             lenght++;
  41.         }
  42.         return lenght;
  43.     }
  45.     private int[] radixSort(int[] arr, int maxDigit) {
  46.         int mod = 10;
  47.         int dev = 1;
  49.         for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
  50.             // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
  51.             int[][] counter = new int[mod * 2][0];
  53.             for (int j = 0; j < arr.length; j++) {
  54.                 int bucket = ((arr[j] % mod) / dev) + mod;
  55.                 counter[bucket] = arrayAppend(counter[bucket], arr[j]);
  56.             }
  58.             int pos = 0;
  59.             for (int[] bucket : counter) {
  60.                 for (int value : bucket) {
  61.                     arr[pos++] = value;
  62.                 }
  63.             }
  64.         }
  66.         return arr;
  67.     }
  69.     /**
  70.      * 自动扩容，并保存数据
  71.      *
  72.      * @param arr
  73.      * @param value
  74.      */
  75.     private int[] arrayAppend(int[] arr, int value) {
  76.         arr = Arrays.copyOf(arr, arr.length + 1);
  77.         arr[arr.length - 1] = value;
  78.         return arr;
  79.     }
  80. }

3. PHP 代码实现

  1. function radixSort($arr, $maxDigit = null)
  2. {
  3.     if ($maxDigit === null) {
  4.         $maxDigit = max($arr);
  5.     }
  6.     $counter = [];
  7.     for ($i = 0; $i < $maxDigit; $i++) {
  8.         for ($j = 0; $j < count($arr); $j++) {
  9.             preg_match_all('/\d/', (string) $arr[$j], $matches);
  10.             $numArr = $matches[0];
  11.             $lenTmp = count($numArr);
  12.             $bucket = array_key_exists($lenTmp - $i - 1, $numArr)
  13.                 ? intval($numArr[$lenTmp - $i - 1])
  14.                 : 0;
  15.             if (!array_key_exists($bucket, $counter)) {
  16.                 $counter[$bucket] = [];
  17.             }
  18.             $counter[$bucket][] = $arr[$j];
  19.         }
  20.         $pos = 0;
  21.         for ($j = 0; $j < count($counter); $j++) {
  22.             $value = null;
  23.             if ($counter[$j] !== null) {
  24.                 while (($value = array_shift($counter[$j])) !== null) {
  25.                     $arr[$pos++] = $value;
  26.                 }
  27.           }
  28.         }
  29.     }
  31.     return $arr;
  32. }