Java桶排序之基数排序详解

基本概念

基数排序（Radix Sort），又称桶排法（Bucket Sort），是一种非比较型整数排序算法。其思想是将一个数字序列拆分成多个数字进行比较排序，从个位开始，逐层进行排序，直到最高位排序完成。

实现步骤

1. 初始化10个桶，代表数字0到9；
2. 按照从低位到高位的顺序进行排序，首先比较个位，然后比较十位，以此类推，直到最高位；
3. 把每次排序后得到的结果依次放回原序列中，重复第2步排序，直至最高位排序完成。

代码实现

以下为Java代码实现：

import java.util.Arrays;

public class RadixSort {
  public static void radixSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    int exp = 1;
    int max = getMax(arr);
    int[] temp = new int[arr.length];
    while (max / exp > 0) {
      int[] bucket = new int[10];
      for (int i = 0; i < arr.length; i++) {
        bucket[(arr[i] / exp) % 10]++;
      }
      for (int i = 1; i < bucket.length; i++) {
        bucket[i] += bucket[i - 1];
      }
      for (int i = arr.length - 1; i >= 0; i--) {
        temp[bucket[(arr[i] / exp) % 10] - 1] = arr[i];
        bucket[(arr[i] / exp) % 10]--;
      }
      System.arraycopy(temp, 0, arr, 0, arr.length);
      exp *= 10;
    }
  }

  public static int getMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
      max = Math.max(max, arr[i]);
    }
    return max;
  }

  public static void main(String[] args) {
    int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    System.out.println("排序前：" + Arrays.toString(arr));
    radixSort(arr);
    System.out.println("排序后：" + Arrays.toString(arr));
  }
}

示例解析

假设有以下数组：

{25, 34, 12, 10, 23, 45, 56, 74}

首先比较个位数，这个数组中个位数分别是：

{5, 4, 2, 0, 3, 5, 6, 4}

按照个位数依次分配到桶里面，桶的数量 = 0 ~ 9，将桶中元素复写到原数组中，原数组变成：

{10, 12, 23, 34, 25, 45, 56, 74}

接下来比较十位数，这个数组中十位数分别是：

{2, 3, 1, 0, 2, 4, 5, 7}

重复上述操作，依次分配到桶中，将桶中元素复写到原数组中，原数组变成：

{10, 12, 23, 25, 34, 45, 56, 74}

最后按照百位数比较排序，由于没有百位数，所以排序已完成，最终得到排序后的数组：

{10, 12, 23, 25, 34, 45, 56, 74}

总结

基数排序是一种非常高效的排序算法，它的时间复杂度为O(kn)，其中k为数字的最高位数，n为数字个数，相较于快速排序的平均时间复杂度O(nlogn)更具优势。