基本介绍
基数排序与其他排序方法不同，它不需要比较关键字的大小。它是根据关键字中各位(个十百千万)的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
排序思想
我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。所以我们不妨把0~9视为10个桶。我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
* 基数排序
*
* @param arr
*/
public static void radixSort(int[] arr) {
// 定义十个桶，用来表示个位/十位/百位/...，0-9 十种情况
int[][] buckets = new int[10][arr.length];
// 定义一个二维数组，用来表示各个桶的元素最大下标
int[] indexOfBuckets = new int[10];
// 遍历处理个位、十位、百位...情况，重排序原始数组
for (int i = 0, n = 1; i < getMaxLength(arr); i++, n *= 10) {
// 1. 遍历每个数，放在对应的桶中
for (int j : arr) {
// 取出所在位数对应的值
int digital = (j / n) % 10;
// 将数放在对应的桶中
buckets[digital][indexOfBuckets[digital]] = j;
// 桶下标+1
indexOfBuckets[digital]++;
}
// 2. 遍历每个桶的元素，将数放到原始数组中
int m = 0;
for (int j = 0; j < 10; j++) {
for (int k = 0; k < indexOfBuckets[j]; k++) {
arr[m++] = buckets[j][k];
}
}
// 将每个桶的下标置0
for (int j = 0; j < 10; j++) {
indexOfBuckets[j] = 0;
}
}
}
|