基数排序
基数排序的python实现
基数排序
基数排序是一种非比较型排序算法，其原理是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
算法步骤
- 找出待排序的数组中最大数，并取得这个数的位数；
- 计算出位数；
- 按照位数排序；
- 合并；
- 返回结果；
- 重复步骤2~5直到所有位数排序完成。
CODE
Python
def cardinality_sort(arr: List) -> List:
if len(arr) <= 1:
return arr
max_val = max(arr)
bucket = [[] for _ in range(10)]
arr = [str(x) for x in arr]
max_len = len(str(max_val))
arr = [x.zfill(max_len) for x in arr]
for i in range(max_len - 1, -1, -1):
for x in arr:
bucket[int(x[i])].append(x)
arr = [item for sublist in bucket for item in sublist]
bucket = [[] for _ in range(10)]
return [int(x) for x in arr]Java
public class RadixSort {
public static int[] radixSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr;
}
int maxVal = arr[0];
for (int num : arr) {
if (num > maxVal) {
maxVal = num;
}
}
int maxLen = String.valueOf(maxVal).length();
List<List<String>> buckets = new ArrayList<>(10);
for (int i = 0; i < 10; i++) {
buckets.add(new ArrayList<>());
}
String[] strArr = new String[arr.length];
for (int i = 0; i < arr.length; i++) {
strArr[i] = String.format("%0" + maxLen + "d", arr[i]);
}
for (int i = maxLen - 1; i >= 0; i--) {
for (String numStr : strArr) {
int digit = numStr.charAt(i) - '0';
buckets.get(digit).add(numStr);
}
int index = 0;
for (List<String> bucket : buckets) {
for (String num : bucket) {
strArr[index++] = num;
}
bucket.clear();
}
}
int[] sortedArr = new int[arr.length];
for (int i = 0; i < strArr.length; i++) {
sortedArr[i] = Integer.parseInt(strArr[i]);
}
return sortedArr;
}
}