基数排序是一种排序算法，它通过首先对相同位值的各个数字进行分组来对元素进行排序。然后，根据元素的递增/递减顺序对元素进行排序。
假设我们有一个包含 8 个元素的数组。首先，我们将根据单位位置的值对元素进行排序。然后，我们将根据第十位的值对元素进行排序。这个过程一直持续到最后一个重要的地方。

设初始数组为[121, 432, 564, 23, 1, 45, 788]。如下图所示按照基数排序。

基数排序（Radix Sort） - 图1
基数排序的工作

请在阅读本文之前先了解计数排序，因为计数排序是基数排序中的一种中间排序。

算法的图解

  1. 找到数组中最大的元素，即 最大值. 让X成为 中的位数max。X计算是因为我们必须遍历所有元素的所有重要位置。

在这个数组中[121, 432, 564, 23, 1, 45, 788]，我们有最大的数字 788。它有 3 位数字。因此，循环应该达到数百个位置（3 次）。

  1. 现在，一个一个地浏览每一个重要的地方。
    使用任何稳定的排序技术对每个重要位置的数字进行排序。我们为此使用了计数排序。
    根据单位位数字 ( X=0)对元素进行排序。
基数排序（Radix Sort） - 图2
使用计数排序根据单位位置对元素进行排序
  1. 现在，根据十位数字对元素进行排序。 | 基数排序（Radix Sort） - 图3 | | —- | | 根据十位对元素进行排序 |
  1. 最后，根据百位的数字对元素进行排序。 | 基数排序（Radix Sort） - 图4 | | —- | | 根据数百个位置对元素进行排序 |

算法的伪码

  1. radixSort(array)
  2.   d <- maximum number of digits in the largest element
  3.   create d buckets of size 0-9
  4.   for i <- 0 to d
  5.     sort the elements according to ith place digits using countingSort
  7. countingSort(array, d)
  8.   max <- find largest element among dth place elements
  9.   initialize count array with all zeros
  10.   for j <- 0 to size
  11.     find the total count of each unique digit in dth place of elements and
  12.     store the count at jth index in count array
  13.   for i <- 1 to max
  14.     find the cumulative sum and store it in count array itself
  15.   for j <- size down to 1
  16.     restore the elements to array
  17.     decrease count of each element restored by 1

算法的实现

  1. // Radix Sort in Java Programming
  3. import java.util.Arrays;
  5. class RadixSort {
  7.   // Using counting sort to sort the elements in the basis of significant places
  8.   void countingSort(int array[], int size, int place) {
  9.     int[] output = new int[size + 1];
  10.     int max = array[0];
  11.     for (int i = 1; i < size; i++) {
  12.       if (array[i] > max)
  13.         max = array[i];
  14.     }
  15.     int[] count = new int[max + 1];
  17.     for (int i = 0; i < max; ++i)
  18.       count[i] = 0;
  20.     // Calculate count of elements
  21.     for (int i = 0; i < size; i++)
  22.       count[(array[i] / place) % 10]++;
  24.     // Calculate cumulative count
  25.     for (int i = 1; i < 10; i++)
  26.       count[i] += count[i - 1];
  28.     // Place the elements in sorted order
  29.     for (int i = size - 1; i >= 0; i--) {
  30.       output[count[(array[i] / place) % 10] - 1] = array[i];
  31.       count[(array[i] / place) % 10]--;
  32.     }
  34.     for (int i = 0; i < size; i++)
  35.       array[i] = output[i];
  36.   }
  38.   // Function to get the largest element from an array
  39.   int getMax(int array[], int n) {
  40.     int max = array[0];
  41.     for (int i = 1; i < n; i++)
  42.       if (array[i] > max)
  43.         max = array[i];
  44.     return max;
  45.   }
  47.   // Main function to implement radix sort
  48.   void radixSort(int array[], int size) {
  49.     // Get maximum element
  50.     int max = getMax(array, size);
  52.     // Apply counting sort to sort elements based on place value.
  53.     for (int place = 1; max / place > 0; place *= 10)
  54.       countingSort(array, size, place);
  55.   }
  57.   // Driver code
  58.   public static void main(String args[]) {
  59.     int[] data = { 121, 432, 564, 23, 1, 45, 788 };
  60.     int size = data.length;
  61.     RadixSort rs = new RadixSort();
  62.     rs.radixSort(data, size);
  63.     System.out.println("Sorted Array in Ascending Order: ");
  64.     System.out.println(Arrays.toString(data));
  65.   }
  66. }

算法复杂度

时间复杂度
最好的 O(n+k)
最差 O(n+k)
平均 O(n+k)
空间复杂度 O(max)
稳定 是的

由于基数排序是一种非比较算法，因此它相比比较排序算法具有优势。对于使用计数排序作为中间稳定排序的基数排序，时间复杂度为O(d(n+k))。

这里，d是循环数，O(n+k)是计数排序的时间复杂度。因此，基数排序具有比O(nlog n)比较排序算法更好的线性时间复杂度。如果我们采用非常大的数字或其他基数，如 32 位和 64 位数字，那么它可以在线性时间内执行，但是中间排序需要很大的空间。这使得基数排序空间效率低下。这就是为什么在软件库中不使用这种排序的原因。

算法的应用

  • DC3 算法 (Kärkkäinen-Sanders-Burkhardt) 同时制作后缀数组。
  • 有大范围数字的地方。

相似的算法

  1. 快速排序
  2. 归并排序
  3. 桶排序
  4. 计数排序