Java实现基数排序，解决负数也可以排序
/*
* 基数序 解决不能负数的问题
*/
public static void negative_radix_sortin(int[] str) {
// 桶 10个桶 每个桶的最大容量默认为数组长度
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 < str.length; a++) {
if (str[a] < 0) {
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_number; 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 < positive_number; b++, u *= 10) {
for (int i = 0; i < positive_number; 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 < capacity.length; k++) {
if (capacity[k] != 0) {
for (int p = 0; p < capacity[k]; p++) {
positive_arr[d] = bucket[k][p];
d++;
}
}
// 注意：清零
capacity[k] = 0;
}
}
// 排序负数数组 正数差不多 注意最后取出数据的时候 才大到小 不再是从小到大
for (int b = 0, u = 1; b < negative_number; b++, u *= 10) {
for (int i = 0; i < negative_number; i++) {
int base = negative_arr[i] / u % 10;
bucket[base][capacity[base]] = negative_arr[i]; // 放进第四个桶中 的第一几个当前容量位置
capacity[base]++;
}
int d = 0;
for (int k = capacity.length - 1; k >= 0; k--) {
if (capacity[k] != 0) {
for (int p = 0; p < capacity[k]; p++) {
negative_arr[d] = bucket[k][p];
d++;
}
}
// 注意：清零
capacity[k] = 0;
}
}
// 把负数数组转化成负数 覆盖给原来的数组（从0开始）
int c = 0;
for (int e = 0; e < negative_number; e++) {
str[c] = negative_arr[e] / (-1);
c++;
}
// 正数接上原来数组
for (int t = 0; t < positive_number; t++) {
str[c] = positive_arr[t];
c++;
}
}