社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
private static void radixSort(int[] array) {
/*定义一个二维数组,表示10个桶,每个桶是一位数组*/
/*说明:
* 1、二维数组包含10个以为数组
* 2、为了防止在放入数据的时候,数据溢出,则每个一位数组(桶),大小定义为array.length
* 3、基数排序是使用空间换时间的经典算法*/
int[][] bucket = new int[10][array.length];
/*为了记录每个桶中,实际存放了多少个数据,定义一个一维数组记录每个桶中的数组个数
* eg:bucketElementsCount[0],记录的是放入bucket[0]中的数据个数*/
int[] bucketElementsCount = new int[10];
/*获取数组中最大值,默认数组内的第一个元素为最大值*/
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
/*获取最大数据的最大位数*/
int lengthMax = (max + "").length();
/*循环数据的长度,第一轮取个位,第二轮取十位,依次类推*/
for (int i = 0, m = 1; i < lengthMax; i++, m *= 10) {
for (int j = 0; j < array.length; j++) {
/*取相应位数的模值*/
int digitalNumber = array[j] / m % 10;
/*根据模值将数据依次放入对应的桶中*/
bucket[digitalNumber][bucketElementsCount[digitalNumber]++] = array[j];
}
/*用于记录数组中的索引位置*/
int index = 0;
/*依次取出桶中的元素,还原至数组中*/
for (int k = 0; k < bucket.length; k++) {
/*判断各个桶中的元素是否为0,不为0 则将数据还原至数组*/
if (bucketElementsCount[k] != 0) {
/*bucketElementsCount[k]代表编号为k的桶中的数据个数*/
for (int n = 0; n < bucketElementsCount[k]; n++) {
array[index++] = bucket[k][n];
}
/*数据全部还原之后,将对应编号桶的数据个数置为0,避免影响下一次数据还原,
* 在整个二维数组的赋值过程中,是覆盖过程*/
bucketElementsCount[k] = 0;
}
}
}
}
以上代码过于繁杂,最空间的要求极高,一旦数据量过大之后,很容易出现OutOfMemoryError错误,故原代码可进行简化,
private static void radixSortSimple(int[] arr) {
//临时数组
Integer[] temp = new Integer[arr.length];
//找出目标数组中的最大值、最小值,用于计算有多少位
int maxValue = arr[0];
int minValue = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxValue) {
maxValue = arr[i];
}
if (arr[i] < minValue) {
minValue = arr[i];
}
}
maxValue = Math.max(Math.abs(maxValue), Math.abs(minValue));
/*求出数据的最大位数*/
int maxLen = (maxValue + "").length();
int base = 10;
/*从个位到最高位*/
for (int i = 0, pow = 1; i < maxLen; i++, pow *= base) {
/*定义一个一维数组,代表19个桶,用于存储各个桶中数据的个数,
负数的存在,故需要19个桶*/
int[] bucket = new int[base * 2 - 1];
for (int j = 0; j < arr.length; j++) {
/*根据余数来计算桶的编号,并存储各个桶中数据的总数
* 计算桶的编号:arr[j] / pow % base
* 计算对应编号在数组内的索引:arr[j] / pow % base + base - 1
* bucket[1] = 8,代表编号为 -8 这个桶内一共有8个元素*/
bucket[arr[j] / pow % base + base - 1]++;
}
/*桶是有序的,将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引*/
for (int j = 1; j < bucket.length; j++) {
bucket[j] += bucket[j - 1];
}
/*桶排序属于稳定排序,当数据相同的时候,原数组排在后面的任然会排在后面
* 故此处的循环必须从原数组的末端向前扫描*/
for (int j = arr.length - 1; j >= 0; j--) {
// /*获取数组中的数据*/
// int i1 = arr[j];
// /*对数据取模*/
// int i2 = i1 / pow % base;
// /*获取桶数组的index*/
// int i3 = i2 + base - 1;
// /*获取桶数据*/
// int i4 = bucket[i3];
// /*由于数组index是以0开始的,统计数据是以1开始的,故在对中间数据赋值的时候,index需要偏移一位*/
// temp[--i4] = arr[j];
// /*数据取出之后,需要修改桶中数据统计值,进行减一操作,*/
// bucket[i3] = i4;
/*以上部分是对这段代码的说明*/
int len = --bucket[arr[j] / pow % base + base - 1];
temp[len] = arr[j];
System.out.println("第" + (j + 1) + "次中间数组temp:" + Arrays.toString(temp));
}
/*将中间数组的元素拷贝至数组*/
for (int j = 0; j < arr.length; j++) {
arr[j] = temp[j];
}
System.out.println(Arrays.toString(arr));
}
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!