本教程显示了如何用Java编写Radix排序程序。基数排序也是在O(n)时间运行的线性排序算法之一，例如Counting排序和Bucket排序使Radix排序比在O(n * logn)时间运行的快速排序或者合并排序更快。

基数排序算法

基数排序通过对从最低有效数字到最高有效数字的遍历进行排序而起作用。基数排序也使用存储桶，在每个通行证中，我们需要根据通行证获取数字的位数(1s，10s等)并将这些数字存储在存储桶中。在每遍中，我们都可以使用诸如计数排序之类的稳定排序来对数字进行排序。

Radix排序算法的步骤可总结如下：

• 获取输入数组中的最大数目。
• 从最低有效数字开始迭代最大数量的每个数字，即单位位置向最高有效数字移动。
• 对于数组中的每个元素，获取该位置的数字并将其存储在存储桶数组中。
• 按照该遍中的数字对输入数组元素进行排序。
• 移至下一位并从开始重复。

例如，如果输入数组为[40、25、206、65、457、4、81、74、58、6]，则数组中的最大数量为457，因此1、10和3将有3次通过100个地方。

下图显示了这些通过以及Radix排序所遵循的过程。

Radix Sort Java程序

public class RadixSort {
  public static void main(String[] args) {
    int[] arr = {40, 25, 206, 65, 457, 4, 81, 74, 58, 6};
    System.out.println("Original Array- " + Arrays.toString(arr));
    radixSort(arr);
    System.out.println("Sorted array after Radix sort- " + Arrays.toString(arr));
  }
	
  private static void radixSort(int[] arr){
    //get max element in array
    int max = getMaxElementInArray(arr);
    int position = 1;
    // move from least significant digit 
    // to most significant digit
    while(max/position > 0){
      countingSort(arr, position);
      position *= 10;
    }        
  }
    
  private static int getMaxElementInArray(int[] arr){
    int max = arr[0];
    for(int i = 1; i < arr.length; i++){
      if (arr[i] > max){
          max = arr[i];
      }
    }
    return max;
  }
    
  // Counting sort used to sort array in each pass
  private static void countingSort(int[] arr, int position){
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[n];
        
    //Calculate frequency of each element, put it in count array
    for(int i = 0; i < arr.length; i++){
      count[(arr[i]/position)%10]++;
    }
    // Modify count array to get the final position of elements
    for(int i = 1; i < n; i++){
      count[i] = count[i] + count[i-1];
    }
    
    // Add elements to output array for this pass
    for(int i = n-1; i >=0; i--){
      output[count[(arr[i]/position)%10] - 1] = arr[i];
      count[(arr[i]/position)%10]--;
    }
    // Copy output array to the input for 
    // the next pass of counting sort
    for(int i = 0; i < output.length; i++){
      arr[i] = output[i];
    }
    System.out.println("Array after Counting sort at position " + position 
        		        + " " + Arrays.toString(arr));
  }
}

输出：

Original Array- [40, 25, 206, 65, 457, 4, 81, 74, 58, 6]
Array after Counting sort at position 1 [40, 81, 4, 74, 25, 65, 206, 6, 457, 58]
Array after Counting sort at position 10 [4, 206, 6, 25, 40, 457, 58, 65, 74, 81]
Array after Counting sort at position 100 [4, 6, 25, 40, 58, 65, 74, 81, 206, 457]
Sorted array after Radix sort- [4, 6, 25, 40, 58, 65, 74, 81, 206, 457]

基数排序时间和空间的复杂性

我们知道计数排序的时间复杂度是O(n + k)。在Radix排序计数中，每一遍都使用sort排序，而我们拥有的遍数等于最大数目中的位数。如果数字用d表示，则Radix排序的时间复杂度为O(d *(n + k))。

空间要求也与计数排序的空间复杂度相同。需要具有空格k的计数数组和具有与输入数组相同大小的输出数组。因此，基数排序的空间复杂度为O(n + k)。