基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
1. 基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异案例看大家发的：
- 基数排序：根据键值的每位数字来分配桶；
- 计数排序：每个桶只存储单一键值；
- 桶排序：每个桶存储一定范围的数值；
2. LSD 基数排序动图演示
动图演示
3. JavaScript 代码实现
1
//LSD Radix Sort
2
var counter = [];
3
function radixSort(arr, maxDigit) {
4
var mod = 10;
5
var dev = 1;
6
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
7
for(var j = 0; j < arr.length; j++) {
8
var bucket = parseInt((arr[j] % mod) / dev);
9
if(counter[bucket]==null) {
10
counter[bucket] = [];
11
}
12
counter[bucket].push(arr[j]);
13
}
14
var pos = 0;
15
for(var j = 0; j < counter.length; j++) {
16
var value = null;
17
if(counter[j]!=null) {
18
while ((value = counter[j].shift()) != null) {
19
arr[pos++] = value;
20
}
21
}
22
}
23
}
24
return arr;
25
}
Copied!
4. python 代码实现
1
def radix(arr):
2
3
digit = 0
4
max_digit = 1
5
max_value = max(arr)
6
#找出列表中最大的位数
7
while 10**max_digit < max_value:
8
max_digit = max_digit + 1
9
10
while digit < max_digit:
11
temp = [[] for i in range(10)]
12
for i in arr:
13
#求出每一个元素的个、十、百位的值
14
t = int((i/10**digit)%10)
15
temp[t].append(i)
16
17
coll = []
18
for bucket in temp:
19
for i in bucket:
20
coll.append(i)
21
22
arr = coll
23
digit = digit + 1
24
25
return arr
Copied!
5. Java 代码实现
1
/**
2
* 基数排序
3
* 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
4
*/
5
public class RadixSort implements IArraySort {
6
7
@Override
8
public int[] sort(int[] sourceArray) throws Exception {
9
// 对 arr 进行拷贝，不改变参数内容
10
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
11
12
int maxDigit = getMaxDigit(arr);
13
return radixSort(arr, maxDigit);
14
}
15
16
/**
17
* 获取最高位数
18
*/
19
private int getMaxDigit(int[] arr) {
20
int maxValue = getMaxValue(arr);
21
return getNumLenght(maxValue);
22
}
23
24
private int getMaxValue(int[] arr) {
25
int maxValue = arr[0];
26
for (int value : arr) {
27
if (maxValue < value) {
28
maxValue = value;
29
}
30
}
31
return maxValue;
32
}
33
34
protected int getNumLenght(long num) {
35
if (num == 0) {
36
return 1;
37
}
38
int lenght = 0;
39
for (long temp = num; temp != 0; temp /= 10) {
40
lenght++;
41
}
42
return lenght;
43
}
44
45
private int[] radixSort(int[] arr, int maxDigit) {
46
int mod = 10;
47
int dev = 1;
48
49
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
50
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
51
int[][] counter = new int[mod * 2][0];
52
53
for (int j = 0; j < arr.length; j++) {
54
int bucket = ((arr[j] % mod) / dev) + mod;
55
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
56
}
57
58
int pos = 0;
59
for (int[] bucket : counter) {
60
for (int value : bucket) {
61
arr[pos++] = value;
62
}
63
}
64
}
65
66
return arr;
67
}
68
69
/**
70
* 自动扩容，并保存数据
71
*
72
* @param arr
73
* @param value
74
*/
75
private int[] arrayAppend(int[] arr, int value) {
76
arr = Arrays.copyOf(arr, arr.length + 1);
77
arr[arr.length - 1] = value;
78
return arr;
79
}
80
}
Copied!
6. PHP 代码实现
1
function radixSort($arr, $maxDigit = null)
2
{
3
if ($maxDigit === null) {
4
$maxDigit = max($arr);
5
}
6
$counter = [];
7
for ($i = 0; $i < $maxDigit; $i++) {
8
for ($j = 0; $j < count($arr); $j++) {
9
preg_match_all('/\d/', (string) $arr[$j], $matches);
10
$numArr = $matches[0];
11
$lenTmp = count($numArr);
12
$bucket = array_key_exists($lenTmp - $i - 1, $numArr)
13
? intval($numArr[$lenTmp - $i - 1])
14
: 0;
15
if (!array_key_exists($bucket, $counter)) {
16
$counter[$bucket] = [];
17
}
18
$counter[$bucket][] = $arr[$j];
19
}
20
$pos = 0;
21
for ($j = 0; $j < count($counter); $j++) {
22
$value = null;
23
if ($counter[$j] !== null) {
24
while (($value = array_shift($counter[$j])) !== null) {
25
$arr[$pos++] = $value;
26
}
27
}
28
}
29
}
30
31
return $arr;
32
}
Copied!
Last modified 2yr ago