1. 排序算法分类
十种常见排序算法可以分为两大类：
- 比较类排序： 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
比较类排序算法包括：插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序。 - 非比较类排序： 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
非比较类算法包括：计数排序、桶排序、基数排序。
2. 算法复杂度
k是数字的最大位数，n是序列长度。
3. 相关概念
稳定： 如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定： 如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度： 对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度： 是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
4. 基数排序
4.1 什么是基数排序
（1）通过键值得各个位的值，将要排序的元素分配至一些桶中，达到排序的作用
（2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定排序法
（3）基数排序是桶排序的扩展
4.2 实现原理
所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
4.3 实现步骤
（1）确定数组中的最大元素有几位（MAX）（确定执行的轮数）
（2）创建0-9个桶（桶的底层是队列），因为所有的数字元素都是由0~9的十个数字组成
（3）依次判断每个元素的个位，十位至MAX位，存入对应的桶中，出队，存入原数组；直 至MAX轮结束输出数组。
（4）具体实现步骤如下图：
Java代码实现:
public class RadixSorte {
/**
* 基数排序
*
* @param args
*/
public static void main(String[] args) {
int[] arr = {
11, 12, 3, 43, 87, 11, 9, 0, 76, 35,
21, 22, 33, 11, 22, 345, 543, 321, 123,
456, 987, 789, 876, 12, 23, 3, 1, 9, 999};
radixSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
private static void radixSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// 获取最大值
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 用二维数组模拟桶放入东西，一共有10个桶
int[][] temp = new int[10][arr.length];
// 元素最大值的长度
String maxString = max + "";
int length = maxString.length();
int temp1 = 1;
for (int i = 0; i < length; i++) {
// 用于记录每个桶中放入元素的位置
int[] count = new int[10];
for (int i1 = 0; i1 < arr.length; i1++) {
int i2 = (arr[i1] / temp1) % 10;
temp[i2][count[i2]] = arr[i1];
count[i2]++;
}
temp1 *= 10;
// 将数据取出放入原数组
int sum = 0;
for (int i1 = 0; i1 < count.length; i1++) {
for (int i2 = 0; i2 < count[i1]; i2++) {
arr[sum++] = temp[i1][i2];
}
}
}
}
}
参考资料：
https://www.jianshu.com/p/5bf511e5a648
https://blog.csdn.net/qq_52253798/article/details/122930548
https://blog.csdn.net/weixin_44713306/article/details/123356864
