非比较类排序：不通过比较来决定元素之间的相对次序，它可以突破基于比较排序（冒泡排序、快速排序、堆排序....）的时间下限O( nlogn )，以线性的时间运行，因此也称线性时间非比较类排序。
计数排序
一、什么是计数排序
计数排序是一种非比较排序，主要用于对整数进行排序。其核心是将序列中的元素作为键存储在额外的数组空间中，而该元素的个数作为值存储在数组空间中，然后通过计算输入数组中每个元素出现的次数，然后利用这些计数信息将元素放回原数组，从而完成排序。
二、计数排序的应用场景
计数排序中最大值和最小值之间的差值不能过大，这是因为要防止建立数组时造成的内存浪费。
序列中存在的元素必须是整数，这是因为计数排序的核心是创建一个计数数组来记录每个整数值的出现次数，非整数类型的元素（如浮点数或字符串）无法直接用作计数数组的索引。
例如：年龄、考试成绩等。如果键值有负数和小数的时候要怎么做呢？我们可以将参与排序的关键字与非负整数建立一一对应的关系。
⬆️补充说明：计数排序利用了非负整数可以作为数组的下标。因此参与排序的元素的值不能太大，否则会创建出很大的数组、计算前缀和，这些过程会浪费很多额外的资源。另外元素的的下标是一个非负整数，天然具有顺序性，而通过下标就可以得到每一个数值的个数，通过查询前缀和计数数组就能知道它排好序以后所处的位置。
三、计数排序的思想
计数排序的核心思想是通过直接计数每个元素的出现次数，从而避免比较操作，达到线性时间复杂度的排序效果。
四、计数排序的代码实现
1、检查数据有效性并遍历数组找出最大值
首先，我们需要检查数组中的元素是否都为非负整数，并找到数组中的最大值。这是为了确定计数数组的大小，并确保数据适合计数排序。
int len = nums.length;
int max = nums[0];
// 找到数组中的最大值，并检验数据有效性
for (int i = 1; i < len; i++) {
if (nums[i] > max) {
max = nums[i];
}
// 数据有效性校验，nums[i] 不能小于 0
if (nums[i] < 0) {
throw new IllegalArgumentException("该数组不适合使用计数排序");
}
}2、创建计数数组并统计每个元素的出现次数
根据最大值，创建一个计数数组max + 1。遍历输入数组，对每个元素进行计数，将计数结果存储在计数数组的相应位置。
// 创建计数数组
int[] count = new int[max + 1];
// 遍历原始数组，完成计数
for (int i = 0; i < len; i++) {
count[nums[i]] += 1;
}3、将计数数组转化为前缀和数组
对计数数组进行累加，使每个位置的值表示小于等于该位置对应元素的数量。这样可以确定每个元素在排序后数组中的最终位置。
// 将计数数组改造成前缀和数组
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}4、构建输出数组并复制原始数组
为了写回排序结果，需要对原始数组做一个拷贝。
// 对原始数组做一个拷贝
int[] numsCopy = new int[len];
for (int i = 0; i < len; i++) {
numsCopy[i] = nums[i];
}
// 或者使用 System.arraycopy(nums, 0, numsCopy, 0, len);5、从后向前扫描，依次把元素写回原始数组
从后向前遍历拷贝的数组，根据前缀和数组中的信息，将每个元素放到输出数组的正确位置。这样可以确保排序的稳定性。
// 从后向前扫描，将元素写回原始数组
for (int i = len - 1; i >= 0; i--) {
int position = count[numsCopy[i]] - 1;
nums[position] = numsCopy[i];
count[numsCopy[i]]--;
}完整代码
以下是整合后的完整代码：
public class CountingSort {
public void sort(int[] nums) {
int len = nums.length;
int max = nums[0];
// 找到数组中的最大值，并检验数据有效性
for (int i = 1; i < len; i++) {
if (nums[i] > max) {
max = nums[i];
}
// 数据有效性校验，nums[i] 不能小于 0
if (nums[i] < 0) {
throw new IllegalArgumentException("该数组不适合使用计数排序");
}
}
// 创建计数数组
int[] count = new int[max + 1];
// 遍历原始数组，完成计数
for (int i = 0; i < len; i++) {
count[nums[i]] += 1;
}
// 将计数数组改造成前缀和数组
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 对原始数组做一个拷贝
int[] numsCopy = new int[len];
for (int i = 0; i < len; i++) {
numsCopy[i] = nums[i];
}
// 以上步骤使用Java可以用 System.arraycopy(nums, 0, numsCopy, 0, len); 代替
// 从后向前扫描，将元素写回原始数组
for (int i = len - 1; i >= 0; i--) {
int position = count[numsCopy[i]] - 1;
nums[position] = numsCopy[i];
count[numsCopy[i]]--;
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 2, 8, 3, 3, 1};
CountingSort sorter = new CountingSort();
sorter.sort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}五、计数排序-总结
计数排序是非比较排序，作为一种稳定算法，它的时间复杂度是O( n + k )，空间复杂度是O( k )。（ n = nums.size(), k = max - min + 1 )。
时间复杂度是O( n + k )：通过上面的代码可知最终的计数算法花费的时间是3n + k，则时间复杂度是O( n + k )。
空间复杂度是O( k )：如果除去最后的返回数组，则空间复杂度是2k，则空间复杂度是O( k )。
稳定算法：由于统计数组可以知道该索引在原数组中排第几位，在从后向前遍历输入数组时，根据前缀和数组中的信息将每个元素放到输出数组的正确位置，这样可以确保相同元素在排序后的数组中保持原来的相对顺序。
基数排序
一、基数排序的介绍
基数排序比较特殊，它是按照元素的低位先排序，然后收集；再按照次高位排序，然后再收集；以此类推，直至数组中最大值的最高位。具体来说，基数排序通过先对低位优先（LSD, Least significant digital）的关键字进行排序，再对高位优先（MSD, Most significant digital）的关键字进行排序，保证了高优先级关键字相同的情况下，低优先级的排序结果得以保留。因为基数排序使用的子排序算法是稳定的（即不会改变相同关键字的相对顺序），这就保证了最终的排序结果满足优先级的要求。
MSD：先从高位开始进行排序，在每一个关键字上，可采用计数排序。
LSD：先从低位开始进行排序，在每一个关键字上，可采用桶排序。
常见的做法是LSD - 低位优先，对高位这里只做简单介绍，重点介绍低位优先。
二、基数排序的优点和局限性
基数排序的优点
时间复杂度为线性时间
O(kn)，对大规模数据排序非常高效。稳定排序算法，保留相同关键字元素的相对顺序。
不需要复杂的比较操作，适合多关键字排序。
基数排序的局限性
需要额外的空间来存储桶，空间复杂度为
O(n + k)。适用于数据可以分解为多个关键字或位数的情况，不适用于一般的比较排序。
对于关键字长度很大的数据，效率可能不如比较排序。
三、基数排序的思想及步骤
基数排序的核心思想是利用数的每一位来进行多次排序，从而达到对整个数列排序的目的。它的基本思想可以概括为：将待排序元素分解为多个关键字，从最低位开始，逐位进行排序，直到最高位。
我们可以通过一个数组来更真实的了解基数排序的步骤，例如：数组nums = [329, 457, 657, 839, 436, 720, 355]
首先按照个位数字进行一次 稳定排序（相同数字顺序不变），得到
[720, 355, 436, 457, 657, 329, 839]然后按照十位数字进行一次 稳定排序（相同数字顺序不变），得到
[720, 329, 436, 839, 355, 457, 657]然后按照百位数字进行一次 稳定排序（相同数字顺序不变），得到
[329, 355, 436, 457, 657, 720, 839]
四、基数排序的代码实现
1、找出最大的数字
在这一步中，我们需要找到数组中最大的数字，同时进行数据有效性校验，确保所有数字都是非负数。
// 第 1 步：找出最大的数字
int max = nums[0];
for (int i = 0; i < len; i++) {
if (nums[i] > max) {
max = nums[i];
}
// 数据有效性校验，因为要将数值作为 count 的索引用，因此 nums[i] 不能小于 0
if (nums[i] < 0) {
throw new IllegalArgumentException("该数组不适合使用计数排序");
}
}⬆️ 寻找最大值：通过遍历数组，找到其中的最大值，这个最大值决定了我们要进行多少次按位排序。
⬆️ 数据有效性校验：确保数组中的所有元素都是非负的，因为基数排序基于数位进行排序，负数将导致索引错误。
2、计算最大数字的位数
这一步计算出最大数字有几位，决定我们要进行几轮排序。
// 第 2 步：计算出最大的数字有几位，这个数值决定了我们要将整个数组看几遍
int maxLen = getMaxLen(max);getMaxLen 方法：获取一个整数的最大位数，通过不断除以 10，计算出最大数字的位数。
private int getMaxLen(int num) {
int maxLen = 0;
while (num > 0) {
num /= 10;
maxLen++;
// 计算位数：通过不断将数字除以 10，计算出其位数
}
return maxLen;
}3、每一趟都使用计数排序
细节：如何得到数位上的数值？1、先把低位抹去。 2、再取个位（模10即可）。
// 计算数位上的数是几，先取个位，再取十位、百位 ....
int remainder = ( nums[j] / divisor ) % 10;这里我们将数组按每一位进行计数排序，从最低有效位开始，逐位进行排序。
// 第 3 步：每一趟都使用计数排序
int[] count = new int[10];
int[] temp = new int[len];
int divisor = 1;
// 有几位数，外层循环就得执行几次
for (int i = 0; i < maxLen; i++) {
// 每一步都使用计数排序，保证排序结果是稳定的，这一步需要额外空间保存结果集，因此把结果保存在 temp 中
countingSort(nums, temp, divisor, len, count);
System.arraycopy(temp, 0, nums, 0, len);
divisor *= 10;
}⬆️ 初始化计数数组和临时数组：计数数组 count 用于存储每个位上的计数，临时数组 temp 用于存储排序结果。
⬆️ 逐位排序：使用 countingSort 方法按每一位进行计数排序，divisor 从 1 开始，每次乘以 10，依次排序个位、十位、百位等。
countingSort 方法：计数排序，这个方法实现了对数组的计数排序，针对每一位进行排序。
private void countingSort(int[] nums, int[] temp, int divisor, int len, int[] count) {
// 内层循环得把数组从头到尾看一遍
for (int j = 0; j < len; j++) {
// 计算数位上的数是几，先取个位，再十位、百位
int remainder = (nums[j] / divisor) % 10;
count[remainder]++;
}
// 将计数数组变成位置数组
for (int j = 1; j < 10; j++) {
count[j] += count[j - 1];
}
// 从后向前遍历原始数组，稳定排序
for (int j = len - 1; j >= 0; j--) {
int remainder = (nums[j] / divisor) % 10;
int index = count[remainder] - 1;
temp[index] = nums[j];
count[remainder]--;
}
// 重置数组 count，以便下次使用
for (int j = 0; j < 10; j++) {
count[j] = 0;
}
}⬆️ 计数：计算每个数位上数字出现的次数，并存储在 count 数组中。
⬆️ 位置计算：通过累加计数数组，计算每个数字应放置的位置。
⬆️ 排序：从后向前遍历原始数组，将每个数字放在其正确位置，以确保稳定排序。
⬆️ 重置计数数组：清空 count 数组，为下一位排序做准备。
4、完整代码
public class RadixSort {
public void sort(int[] nums) {
int len = nums.length;
// 第 1 步：找出最大的数字
int max = nums[0];
for (int i = 0; i < len; i++) {
if (nums[i] > max) {
max = nums[i];
}
// 数据有效性校验，因为要将数值作为 count 的索引用，因此 nums[i] 不能小于 0
if (nums[i] < 0) {
throw new IllegalArgumentException("该数组不适合使用基数排序");
}
}
// 第 2 步：计算出最大的数字有几位，这个数值决定了我们要将整个数组看几遍
int maxLen = getMaxLen(max);
// 第 3 步：每一趟都使用计数排序
int[] count = new int[10];
int[] temp = new int[len];
int divisor = 1;
// 有几位数，外层循环就得执行几次
for (int i = 0; i < maxLen; i++) {
// 每一步都使用计数排序，保证排序结果是稳定的，这一步需要额外空间保存结果集，因此把结果保存在 temp 中
countingSort(nums, temp, divisor, len, count);
System.arraycopy(temp, 0, nums, 0, len);
divisor *= 10;
}
}
/**
*
* @param nums 原始数组
* @param temp 在计数排序的过程中使用的辅助数组，这一次基于 divisor 关键字的排序结果存在这里
* @param divisor 当前位的除数（1表示个位，10表示十位，100表示百位）
* @param len 原始数组的长度
* @param count 计数数组
*/
private void countingSort(int[] nums, int[] temp, int divisor, int len, int[] count) {
// 内层循环得把数组从头到尾看一遍
for (int j = 0; j < len; j++) {
// 计算数位上的数是几，先取个位，再十位、百位
int remainder = (nums[j] / divisor) % 10;
count[remainder]++;
}
// 将计数数组变成位置数组
for (int j = 1; j < 10; j++) {
count[j] += count[j - 1];
}
// 从后向前遍历原始数组，稳定排序
for (int j = len - 1; j >= 0; j--) {
int remainder = (nums[j] / divisor) % 10;
int index = count[remainder] - 1;
temp[index] = nums[j];
count[remainder]--;
}
// 重置数组 count，以便下次使用
for (int j = 0; j < 10; j++) {
count[j] = 0;
}
}
/**
* 获取一个整数的最大位数
*
* @param num
* @return
*/
private int getMaxLen(int num) {
int maxLen = 0;
while (num > 0) {
num /= 10;
maxLen++;
}
return maxLen;
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
RadixSort radixSort = new RadixSort();
radixSort.sort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}五、基数排序-总结
时间复杂度是O(d*(n+k))：通过上面的代码可知，基数排序对每一位都进行一次计数排序，一趟分配的时间复杂度为O(n)，一趟收集的时间复杂度为O(r+n)，假设数组中最大的数有 d 位，则基数排序需要进行 d 次计数排序，时间复杂度为O(d(2n+r))，即O(d(n+r)).
空间复杂度是O(n+k)：基数排序的空间复杂度包括用于存储计数数组和临时数组的空间。计数数组的大小为 k，临时数组的大小为 n。因此，基数排序的空间复杂度为 O(n + k)。
稳定算法：基数排序是稳定的排序算法。由于每次排序时会根据当前位上的值将元素放置在临时数组中，并且从后向前遍历原始数组来保证相同元素在排序后的数组中保持原来的相对顺序。这样确保了相同元素在每次排序中的相对位置不变，从而保持了排序的稳定性。