JAVA
/** * Radix Sort * * @param arr * @return */ public static int[] RadixSort(int[] arr) { if (arr.length < 2) { return arr; } int N = 1; int maxValue = arr[0]; for (int element : arr) { if (element > maxValue) { maxValue = element; } } while (maxValue / 10 != 0) { maxValue = maxValue / 10; N += 1; } for (int i = 0; i < N; i++) { List<List<Integer>> radix = new ArrayList<>(); for (int k = 0; k < 10; k++) { radix.add(new ArrayList<Integer>()); } for (int element : arr) { int idx = (element / (int) Math.pow(10, i)) % 10; radix.get(idx).add(element); } int idx = 0; for (List<Integer> l : radix) { for (int n : l) { arr[idx++] = n; } } } return arr; }Python
def RadixSort(arr): if len(arr) < 2: return arr maxValue = arr[0] N = 1 for i in range(len(arr)): if arr[i] > maxValue: maxValue = arr[i] while maxValue // 10 != 0: maxValue = maxValue//10 N += 1 for n in range(N): radix = [[] for i in range(10)] for i in range(len(arr)): idx = arr[i]//(10**n) % 10 radix[idx].append(arr[i]) idx = 0 for j in range(len(radix)): for k in range(len(radix[j])): arr[idx] = radix[j][k] idx += 1 return arr 算法分析稳定性：稳定
时间复杂度：最佳：O(n×k) 最差：O(n×k) 平均：O(n×k)
空间复杂度：O(n+k)
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值
参考文章https://www.cnblogs.com/guoyaohua/p/8600214.html
https://en.wikipedia.org/wiki/Sorting_algorithm
https://sort.hust.cc/