-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRadixSort.java
More file actions
64 lines (61 loc) · 2.25 KB
/
RadixSort.java
File metadata and controls
64 lines (61 loc) · 2.25 KB
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package basic.sort;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 基数排序（非比较排序）
* 基本思想：将整数按照位数切割成不同的数字，然后每位分别比较
* 实现逻辑：求出最大值的位数，将其他待比较数值的前面补0，然后从最低位开始，将其分到0~9范围内的10个桶中，然后按照桶顺序及桶内的顺序取出，这样就完成了一次排序，这样一直迭代直到最高位，数组就变成了一个有序队列。
* 算法限制：基数排序可以用来比较字符串或数字，是计数排序和桶排序的改进版,
* Time Complexity:O(N*K)，K为最高位的位数
* Space Complexity:O(N)
*
* @author JunjunYang
* @date 2019/10/25 10:32
*/
public class RadixSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) {
if (sourceArray.length <= 1) return sourceArray;
int[] array = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(array);
//创建0~9的桶
int bucketNum = 10;
ArrayList<Integer>[] bucket = new ArrayList[bucketNum];
for (int i = 0; i < bucketNum; i++) bucket[i] = new ArrayList<>();
int mod = 10;
int div = 1;
//多次分桶并排序
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
for (int val : array) {
int index = (val % mod) / div;
bucket[index].add(val);
}
int pos = 0;
for (ArrayList arrayList : bucket) {
for (Object val : arrayList) {
array[pos++] = (int) val;
}
//注意每次排序完后需要清空list，以便下次迭代使用
arrayList.clear();
}
}
return array;
}
/**
* 最大值的位数
*
* @param array
* @return
*/
public int getMaxDigit(int[] array) {
int maxValue = array[0];
for (int val : array) {
if (val > maxValue) maxValue = val;
}
int maxDigit = 1;
while ((maxValue /= 10) != 0) {
maxDigit++;
}
return maxDigit;
}
}