上面 Java 版本有点问题：
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];
....
}
counter 数组的定义，会随着 mod 不断乘 10 变得越来越大。理论上 counter 数组只需要容量为 20 就可以表示负数与正数的所有数字字符。
另外，方法 getMaxDigit 计算数字的最大长度，只考虑到最大值的长度，没有考虑当存在负数时，最小值负数的字符长度也可能是最大的长度。
更新后的版本：
/** 基数排序 */
public class RadixSort {
public int[] sort(int[] arr) {
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/** * 获取最高位数 */ private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
int minValue = getMinValue(arr);
return Math.max(getNumLength(maxValue), getNumLength(minValue));
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
private int getMinValue(int[] arr) {
int minValue = arr[0];
for (int value : arr) {
if (minValue > value) {
minValue = value;
}
}
return minValue;
}
protected int getNumLength(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10) int[][] counter = new int[20][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + 10;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/** * 自动扩容，并保存数据 * * @param arr * @param value */ private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}散步留馨 散步留馨
she***nglife@163.com
4年前 (2022-04-13)