排序算法----基数排序
1.基本思想
基数排序的基本思想：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
2.基数排序的代码实现
package com.yishuai.sort;
import java.util.Arrays;
/**
* @author yishuai
* @description 基数排序算法
* @date 2021/3/23 10:02 下午
*/
public class Radix {
public static void main(String[] args) {
int[] initial = {15, 159, 552, 328, 976, 333, 312, 4, 799};
radixSort(initial);
System.out.println(Arrays.toString(initial));
}
/**
* 基数排序(经典的用空间换时间的算法，速度非常快)：
* 第一步：确定数组中最大数的位数
* 第二步：定义二维数组，十个一维数组作为十个桶，桶的大小是数组的长度
* 第三步：定义一个大小为10的一位数组，用来记录每个桶里面数个数
* 第四步：分别取个位、十位、百位...，分别放入对应序号的桶内
* 第五步：从小到大遍历每一个桶，依次把桶里的数据放入到原来数组中
* 遍历完最后一位时，则代表排序完成。
*/
public static void radixSort(int[] initial) {
//假设第一位就是最大的，然后循环遍历所有的数，把最大数找出来
int maxSize = initial[0];
for (int i = 1; i < initial.length; i++) {
if (maxSize < initial[i]) {
maxSize = initial[i];
}
}
//确定最大数后，通过转换成字符串，然后取字符串长度，就知道最大有几位数
int maxLength = (maxSize + "").length();
//第二步：定义桶的个数和大小,、
// 取到数组的长度，是为了防止所以元素都在一个桶里，导致数组越界
int[][] bucket = new int[10][initial.length];
//第三步：定义记录每个桶里元素个数的一维数组
int[] count = new int[10];
//第四步：分别取个、十、百...的数据，放入桶里，开始排序
//i为0代表各位，1代表十位，直到遍历到最大位数
//n是用来表示个位数、十位数等... 取10的倍数
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
//把数组里面的每个数都遍历出来，然后放到桶子里面
for (int j = 0; j < initial.length; j++) {
/**
* digit：位数
* /1代表是数本身，%10表示取10的余数，代表取出个位数
* /10代表取出数除以10的商，然后%10，代表取出了十位数
* /100代表取出数除以100的商，就是百位数本身，百位数是一位数，一位数再%10还是本身
* 这是为了找规律，凑出来的数据
*/
int digit = initial[j] / n % 10;
//取出digit号桶子，然后往里面添加数据，同时count对应的记录数据+1
//count[digit]是代表桶里本来的数据已经到了多少位，往上面添加即可
bucket[digit][count[digit]++] = initial[j];
}
int num = 0;
//第五步：把桶里的每个元素，一次放到数组中去
for (int k = 0; k < 10; k++) {
//通过计数的数组，把不为0的数组里面的数一次遍历出来
if (count[k] != 0) {
for (int j = 0; j < count[k]; j++) {
//把第i个不为空的桶里的，第j个数据，放到数组中
initial[num++] = bucket[k][j];
}
}
//每次把个位、十位...数据取出来后，把桶子里面的计数清空
// 也就代表着清空了桶子里的数，这样下次又会从第0个开始
count[k] = 0;
}
System.out.println(Arrays.toString(initial));
}
}
}
3.基数排序存在的问题
基数排序是对传统桶排序的扩展，速度很快.
基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
基数排序是稳定的。
[注:假定在待排序的记录序列中， 存在多个具有相同的关键字的记录，若经过排序，这些 记录的相对次序保持不变，即在原序列中， r[i]=r[j]， 且 r[i]在 r[j]之前， 而在排序后的序列中， r[i]仍在 r[j]之前， 则称这种排序算法是稳定的；否则称为不稳定的]
有负数的数组，我们一般不用基数排序来进行排序，如果要支持负数，还要进行进一步的改善