Java实现基数排序（解决负数也可以排序）
2021-02-20 09:20
标签：int void number bucket 最小 取出 注意 ++ 解决 Java实现基数排序（解决负数也可以排序） 标签：int void number bucket 最小 取出 注意 ++ 解决 原文地址：https://www.cnblogs.com/miwujun/p/12683045.html
* 基数序 解决不能负数的问题
*/
public static void negative_radix_sortin(int[] str) {
int[][] bucket = new int[10][str.length];
// 每个桶的当前容量
int[] capacity = new int[10];
// 注意：正数负数共用10个桶 不要再重新定义 节约内存 因为每次都有清理空
int negative_number = 0;// 记录负数个数
int positive_number = 0;// 记录正数个数
int[] negative_arr = new int[str.length];// 存放负数
int[] positive_arr = new int[str.length];// 存放正数
// 记录正数最大值 和负数最小值 用于记录长度
int max = positive_arr[0];
int min = negative_arr[0];
// 先把原数组分成一个负数数组 和一个正数数组 并找出正数最大值
for (int a = 0; a if (str[a] negative_arr[negative_number] = str[a];
negative_number += 1;
} else {
positive_arr[positive_number] = str[a];
positive_number += 1;
}
// 找出正数最大值
if (str[a] > max) {
max = str[a];
}
for (int r = 0; r negative_arr[r] = negative_arr[r] / (-1);
// 此时的负数数组已经是正数
if (negative_arr[r] > min) {
min = negative_arr[r];
}
}
int max_length = (max + "").length();
int min_length = (min + "").length();
for (int b = 0, u = 1; b for (int i = 0; i int base = positive_arr[i] / u % 10; // 比如基数为 4
// 将基数按照规则放进桶中
bucket[base][capacity[base]] = positive_arr[i]; // 放进第四个桶中 的第一几个当前容量位置
capacity[base]++; // 容量增加
}
// 取出数据
int d = 0;
for (int k = 0; k if (capacity[k] != 0) {
for (int p = 0; p positive_arr[d] = bucket[k][p];
d++;
}
}
// 注意：清零
capacity[k] = 0;
}
for (int b = 0, u = 1; b for (int i = 0; i int base = negative_arr[i] / u % 10;
bucket[base][capacity[base]] = negative_arr[i]; // 放进第四个桶中 的第一几个当前容量位置
capacity[base]++;
}
int d = 0;
if (capacity[k] != 0) {
for (int p = 0; p negative_arr[d] = bucket[k][p];
d++;
}
}
// 注意：清零
capacity[k] = 0;
}
int c = 0;
for (int e = 0; e str[c] = negative_arr[e] / (-1);
c++;
}
// 正数接上原来数组
for (int t = 0; t str[c] = positive_arr[t];
c++;
}
下一篇：二维数组中的查找