Java基数排序(radix sort)原理及用法解析

简介

基数排序(radix sort)是一种线性时间非比较排序算法。该算法按照元素的每个位数进行排序。

对于待排序的整数集合，基数排序将集合中的元素按照它们的个位、十位、百位……的大小排序（可以理解为在固定位数的情况下逐个进行桶排序）。

基数排序的时间复杂度为 $O(d \cdot (n+k))$，其中 $d$ 是数字的最长位数，$n$ 是待排序数字的数量，$k$ 是桶的个数。

实现思路

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；

3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

   • 稳定排序：从小到大排序时，计数数组的累加，从大到小排序时，计数数组的逆序累加。

4. 将前一个排序的数组项，由于排序时用了计数排序，已经是有序的，再次将这个数组，按照下一位重新排序；

5. 重复步骤4，直到整个数组按照要求有序；

示例

假设我们有以下需要排序的数组：

int[] arr = {53, 3, 542, 748, 14, 214, 154, 63, 616};

1. 取得数组中的最大数，并取得位数：

```java
int max = arr[0];
for (int i = 1; i < arr.length; i++){
if (arr[i] > max) {
max = arr[i];
}
}

// 取到max值为748，则d=3
int d = 0;
while (max > 0){
d++;
max /= 10;
}
```

1. 从最低位开始取每个位组成radix数组：

```java
int[][] bucket = new int[10][arr.length];
int[] counts = new int[10];

for (int i = 0, divide = 1; i < d; i++, divide *= 10) {
for (int j = 0; j < arr.length; j++) {
int num = (arr[j] / divide) % 10;
bucket[num][counts[num]] = arr[j];
counts[num]++;
}

  int index = 0;
  for (int j = 0; j < counts.length; j++) {
     if (counts[j] != 0) {
        for (int k = 0; k < counts[j]; k++) {
           arr[index++] = bucket[j][k];
        }
        counts[j] = 0;
     }
  }

}

System.out.println(Arrays.toString(arr));
```

输出结果为： [3, 14, 53, 63, 154, 214, 542, 616, 748]

1. 排序完成，按照要求有序。

实际应用

基数排序适用于数据范围较小的排序场景，相对于快速排序等算法而言，基数排序的稳定性为优势。

常见应用在整数、字符串等排序需求中，如电话号码排序、字符串排序等。