https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

1. 简介

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

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

2. 实现

实现思路

  1. 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
  2. 然后，从最低位开始，依次进行一次排序。
  3. 这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

wiki基数排序.gif

Java实现

  1. public class RadixSort {
  3.     public int[] sort(int[] sourceArray) throws Exception {
  4.         // 对 arr 进行拷贝，不改变参数内容
  5.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  7.         int maxDigit = getMaxDigit(arr);
  8.         return radixSort(arr, maxDigit);
  9.     }
  12.     //获取最高位数
  13.     private int getMaxDigit(int[] arr) {
  14.         int maxValue = getMaxValue(arr);
  15.         return getNumLenght(maxValue);
  16.     }
  18.     private int getMaxValue(int[] arr) {
  19.         int maxValue = arr[0];
  20.         for (int value : arr) {
  21.             if (maxValue < value) {
  22.                 maxValue = value;
  23.             }
  24.         }
  25.         return maxValue;
  26.     }
  28.     protected int getNumLenght(long num) {
  29.         if (num == 0) {
  30.             return 1;
  31.         }
  32.         int lenght = 0;
  33.         for (long temp = num; temp != 0; temp /= 10) {
  34.             lenght++;
  35.         }
  36.         return lenght;
  37.     }
  39.     private int[] radixSort(int[] arr, int maxDigit) {
  40.         int mod = 10;
  41.         int dev = 1;
  43.         for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
  44.             // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
  45.             int[][] counter = new int[mod * 2][0];
  47.             for (int j = 0; j < arr.length; j++) {
  48.                 int bucket = ((arr[j] % mod) / dev) + mod;
  49.                 counter[bucket] = arrayAppend(counter[bucket], arr[j]);
  50.             }
  52.             int pos = 0;
  53.             for (int[] bucket : counter) {
  54.                 for (int value : bucket) {
  55.                     arr[pos++] = value;
  56.                 }
  57.             }
  58.         }
  60.         return arr;
  61.     }
  64.     //自动扩容，并保存数据
  65.     private int[] arrayAppend(int[] arr, int value) {
  66.         arr = Arrays.copyOf(arr, arr.length + 1);
  67.         arr[arr.length - 1] = value;
  68.         return arr;
  69.     }
  70. }

3. 效率

基数排序的时间复杂度是O(k*n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(nlogn)，k的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小；k决定了进行多少轮处理，而n是每轮处理的操作数目。

  • 时间复杂度: O(k*n)
  • 空间复杂度: O(k+n)

基数排序如果想效率比较高, 则对要排序的数据有要求

  • 数据可以用位的用”位”来分割
  • “位”之间有递进关系
  • 每一位的数据范围不能太大，要可以用线性排序算法来排序

如果不能满足这几点, 基数排序就无法使用