排序上（冒泡/选择/插入）
排序中（归并/堆排/快排）
4.1.7 计数排序（Counting Sort）
基本概念
计数排序是一种非比较排序算法，它不通过比较元素来排序，而是通过统计每个元素出现的次数来实现排序。计数排序适用于已知范围的整数排序，其时间复杂度为O(n+k)，其中k是整数的范围。
计数排序的核心思想是：将输入的数据值转化为键存储在额外开辟的数组空间中，然后依次把计数大于0的元素按顺序填充到结果数组中。
生活中的例子
想象一个班级的考试成绩统计：
- 假设成绩范围是0-100分
- 老师拿到一叠试卷，想按分数从低到高排序
- 老师可以准备101个格子（对应0-100分），每个格子放对应分数的试卷
- 最后从0分开始，依次取出每个格子里的试卷，就得到了排好序的结果
这就是计数排序的基本思想 - 不需要比较元素大小，只需要"数数"。
算法步骤
- 找出范围：确定待排序数组中的最大值和最小值
- 计数：统计数组中每个值出现的次数，存入计数数组
- 排序：根据计数数组，将元素按顺序放回原数组
图解过程
假设我们有数组：[4, 2, 2, 8, 3, 3, 1]
步骤1：找出范围
- 最小值：1
- 最大值：8
- 范围：8-1+1=8（需要8个计数格子）
步骤2：计数
- 创建计数数组count[8]，初始值都是0
- 遍历原数组，对应位置计数加1
原数组：[4, 2, 2, 8, 3, 3, 1]
计数数组（索引是原数组元素值减去最小值）：
count[0] = 1 (对应值1，出现1次)
count[1] = 2 (对应值2，出现2次)
count[2] = 2 (对应值3，出现2次)
count[3] = 1 (对应值4，出现1次)
count[4] = 0 (对应值5，出现0次)
count[5] = 0 (对应值6，出现0次)
count[6] = 0 (对应值7，出现0次)
count[7] = 1 (对应值8，出现1次)
步骤3：排序
- 遍历计数数组，按照计数将元素放回原数组
排序后数组：[1, 2, 2, 3, 3, 4, 8]
优化版本（稳定排序）
为了保证排序的稳定性（相同元素的相对位置不变），可以对计数排序进行优化：
- 累加计数数组，使count[i]表示小于等于i的元素个数
- 从后向前遍历原数组，根据计数数组确定每个元素在排序后数组中的位置
代码实现
public static void countingSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return; // 数组为空或只有一个元素，无需排序
}
// 步骤1：找出最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
// 计算范围
int range = max - min + 1;
// 步骤2：创建并填充计数数组
int[] count = new int[range];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// 步骤3：根据计数数组排序原数组
int index = 0;
for (int i = 0; i < range; i++) {
// 将计数大于0的元素依次填充到原数组
while (count[i] > 0) {
arr[index++] = i + min;
count[i]--;
}
}
}
// 稳定版本的计数排序
public static void stableCountingSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 找出最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];
// 统计每个元素出现的次数
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// 累加计数数组
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// 从后向前遍历原数组，确保稳定性
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
// 将结果复制回原数组
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
性能分析
时间复杂度：O(n + k)，其中n是数组长度，k是整数范围（max-min+1）
- 当k很小时，计数排序的效率非常高
- 当k很大时，计数排序可能不如其他排序算法
空间复杂度：O(k) - 需要额外的计数数组和输出数组（稳定版本）
稳定性：
- 基本版本：稳定
- 优化版本：稳定（通过从后向前遍历确保稳定性）
适用场景
- 排序的数据是有确定范围的整数
- 数据量大但范围小的情况（如对0-100的分数排序）
- 对排序稳定性有要求的场景
计数排序的优缺点
优点：
- 时间复杂度为O(n+k)，优于比较排序的O(n log n)
- 排序稳定
- 适合数据量大但范围小的情况
缺点：
- 只适用于整数排序
- 当数据范围k很大时，空间复杂度高
- 不适合排序范围未知或范围很大的数据
4.1.8 基数排序（Radix Sort）
基本概念
基数排序是一种非比较型整数排序算法，它的核心思想是按照数字的每一个位（个位、十位、百位…）来进行排序。基数排序不是直接比较元素的大小，而是通过分配和收集的过程来实现排序。
基数排序有两种实现方式：
- 最低位优先(LSD - Least Significant Digit)：从最低位（个位）开始，逐位向高位排序
- 最高位优先(MSD - Most Significant Digit)：从最高位开始，逐位向低位排序
通常使用LSD方式，因为它更容易实现且稳定性好。
生活中的例子
想象一下邮局分拣信件的场景：
- 邮局收到大量的信件，需要按照邮政编码排序
- 工作人员先按照邮编的最后一位数字（个位）将信件分成10堆（0-9）
- 然后将这10堆信件合并，保持相对顺序不变
- 接着按照邮编的倒数第二位（十位）再次分成10堆
- 重复这个过程，直到处理完邮编的所有位数
- 最终，所有信件就按照邮编顺序排好了
这就是基数排序的基本思想 - 逐位排序，最终得到完全有序的结果。
算法步骤
- 确定最大位数：找出数组中的最大值，确定它有多少位数
- 逐位排序：从最低位（个位）开始，对每一位进行计数排序
- 重复过程：对十位、百位…依次进行同样的排序，直到处理完所有位数
图解过程
假设我们有数组：[170, 45, 75, 90, 802, 24, 2, 66]
步骤1：确定最大位数
- 最大值是802，有3位数
步骤2：按个位数排序
- 分组：[170, 90, 802, 2] (个位是0或2)，[45, 75, 24] (个位是4或5)，[66] (个位是6)
- 合并：[170, 90, 802, 2, 45, 75, 24, 66]
步骤3：按十位数排序
- 分组：[802, 2] (十位是0)，[24] (十位是2)，[45] (十位是4)，[66] (十位是6)，[170, 75] (十位是7)，[90] (十位是9)
- 合并：[802, 2, 24, 45, 66, 170, 75, 90]
步骤4：按百位数排序
- 分组：[2, 24, 45, 66, 75, 90] (百位是0)，[170] (百位是1)，[802] (百位是8)
- 合并：[2, 24, 45, 66, 75, 90, 170, 802]
排序完成！
代码实现
public static void radixSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return; // 数组为空或只有一个元素，无需排序
}
// 步骤1：找出最大值
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
// 步骤2：计算最大值的位数
int maxDigit = 0;
while (max > 0) {
max /= 10;
maxDigit++;
}
// 步骤3：按照每一位进行排序（从个位开始）
for (int digit = 0; digit < maxDigit; digit++) {
countingSortByDigit(arr, digit);
}
}
// 对数组按照指定的位数进行计数排序
private static void countingSortByDigit(int[] arr, int digit) {
int n = arr.length;
int[] output = new int[n]; // 输出数组
int[] count = new int[10]; // 计数数组（0-9十个数字）
// 统计每个数字出现的次数
for (int i = 0; i < n; i++) {
int digitValue = getDigit(arr[i], digit);
count[digitValue]++;
}
// 累加计数数组，计算每个数字应该放置的位置
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 从后向前遍历原数组，构建输出数组（保证稳定性）
for (int i = n - 1; i >= 0; i--) {
int digitValue = getDigit(arr[i], digit);
output[count[digitValue] - 1] = arr[i];
count[digitValue]--;
}
// 将输出数组复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// 获取数字num的第digit位的值（从个位开始，个位是第0位）
private static int getDigit(int num, int digit) {
// 使用整数除法和取模运算获取指定位的数字
return (num / (int) Math.pow(10, digit)) % 10;
}
性能分析
时间复杂度：O(d * (n + k))
- d是最大数的位数
- n是元素个数
- k是每位数字的范围（十进制数是10）
- 当d很小时，基数排序可以接近O(n)的时间复杂度
空间复杂度：O(n + k)
- 需要额外的输出数组和计数数组
稳定性：稳定
- 基数排序是稳定的排序算法，相同元素的相对位置不会改变
适用场景
- 排序的数据是整数或可以转化为整数的数据
- 数据位数较少，但数据量较大的情况
- 数据取值范围很大，但是位数不多的情况
基数排序的优缺点
优点：
- 可以达到线性时间复杂度O(n)，当位数d很小时
- 排序稳定
- 适合长度相近的数据排序（如电话号码、字符串等）
缺点：
- 只适用于可以分割出独立位的数据，如整数
- 对于负数，需要特殊处理
- 当数据位数很多时，可能不如比较排序算法
- 需要额外的空间来存储中间结果
基数排序与计数排序、桶排序的关系
基数排序、计数排序和桶排序都是非比较排序算法，它们之间有密切的关系：
- 基数排序使用计数排序作为内部排序算法（对每一位进行排序）
- 基数排序可以看作是桶排序的一种特殊实现（每一位有10个桶）
- 这三种排序算法都可以在特定条件下达到线性时间复杂度
4.1.9 桶排序（Bucket Sort）
基本概念
桶排序是一种分治策略的排序算法，其核心思想是将数据分散到有限数量的桶中，每个桶再单独排序。当待排序数据分布均匀时，桶排序可以达到线性时间复杂度。
桶排序的工作原理是将数据范围分成n个大小相同的区间，这些区间被称为桶。然后将数据放入对应的桶中，再对每个桶中的数据进行排序，最后将所有桶中的数据按照顺序合并起来。
生活中的例子
想象一个图书馆整理书籍的场景：
- 图书管理员需要整理一大堆不同类别的书籍
- 首先，管理员准备了几个书架（桶），分别标记为"文学"、“科学”、“历史”、"艺术"等
- 然后，管理员将每本书放入对应类别的书架上
- 接着，管理员对每个书架上的书按照书名字母顺序排序
- 最后，管理员按照书架的顺序（如先文学，再科学…）将所有书籍重新排列
这就是桶排序的基本思想 - 分类、局部排序、合并。
算法步骤
- 创建桶：根据数据范围创建n个空桶
- 分配数据：遍历原始数组，将每个元素放入对应的桶中
- 桶内排序：对每个非空桶内的元素进行排序（可以使用任何排序算法）
- 合并桶：按照桶的顺序，将所有桶中的元素合并成有序数组
图解过程
假设我们有数组：[0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
步骤1：创建桶
- 创建5个桶，每个桶覆盖范围0.2（0-0.2, 0.2-0.4, 0.4-0.6, 0.6-0.8, 0.8-1.0）
步骤2：分配数据
- 桶0（0-0.2）：空
- 桶1（0.2-0.4）：[0.32, 0.33, 0.37]
- 桶2（0.4-0.6）：[0.42, 0.47, 0.52, 0.51]
- 桶3（0.6-0.8）：空
- 桶4（0.8-1.0）：空
步骤3：桶内排序
- 桶1：[0.32, 0.33, 0.37]
- 桶2：[0.42, 0.47, 0.51, 0.52]
步骤4：合并桶
- 最终排序结果：[0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]
代码实现
public static void bucketSort(double[] arr) {
if (arr == null || arr.length <= 1) {
return; // 数组为空或只有一个元素，无需排序
}
int n = arr.length;
// 步骤1：创建桶（这里创建n个桶）
List<List<Double>> buckets = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
buckets.add(new ArrayList<>());
}
// 找出数组中的最大值和最小值
double maxVal = arr[0];
double minVal = arr[0];
for (int i = 1; i < n; i++) {
maxVal = Math.max(maxVal, arr[i]);
minVal = Math.min(minVal, arr[i]);
}
// 计算桶的范围大小
double range = (maxVal - minVal) / n;
if (range == 0) range = 1; // 防止除以零错误
// 步骤2：将数据分配到桶中
for (int i = 0; i < n; i++) {
// 计算元素应该放入哪个桶
int bucketIndex = (int) ((arr[i] - minVal) / range);
// 处理边界情况
if (bucketIndex >= n) {
bucketIndex = n - 1;
}
// 将元素添加到对应的桶中
buckets.get(bucketIndex).add(arr[i]);
}
// 步骤3：对每个桶内部进行排序
for (int i = 0; i < n; i++) {
if (!buckets.get(i).isEmpty()) {
Collections.sort(buckets.get(i)); // 使用Java内置排序
}
}
// 步骤4：将桶中的元素合并回原数组
int index = 0;
for (int i = 0; i < n; i++) {
for (double value : buckets.get(i)) {
arr[index++] = value;
}
}
}
// 针对整数数组的桶排序
public static void bucketSortForIntegers(int[] arr, int bucketSize) {
if (arr == null || arr.length <= 1) {
return;
}
// 找出最大值和最小值
int minValue = arr[0];
int maxValue = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
// 计算桶的数量
int bucketCount = (maxValue - minValue) / bucketSize + 1;
List<List<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
// 将数据分配到桶中
for (int i = 0; i < arr.length; i++) {
int bucketIndex = (arr[i] - minValue) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
// 对每个桶内部进行排序
int currentIndex = 0;
for (int i = 0; i < buckets.size(); i++) {
Integer[] bucketArray = buckets.get(i).toArray(new Integer[0]);
Arrays.sort(bucketArray);
for (int j = 0; j < bucketArray.length; j++) {
arr[currentIndex++] = bucketArray[j];
}
}
}
性能分析
时间复杂度：
- 平均情况：O(n + k)，其中k是桶的数量
- 最坏情况：O(n²)，当所有元素都被分配到同一个桶中时
- 最好情况：O(n)，当元素均匀分布在各个桶中时
空间复杂度：O(n + k)
- 需要额外的空间来存储桶
稳定性：稳定
- 如果桶内排序使用的算法是稳定的，则桶排序也是稳定的
适用场景
- 待排序数据分布比较均匀
- 数据量大但是数据范围有限
- 外部排序（数据太大，无法一次性加载到内存）
桶排序的优缺点
优点：
- 当数据分布均匀时，时间复杂度接近O(n)
- 适合外部排序（数据量大，内存有限）
- 可以并行化处理（不同的桶可以在不同的处理器上排序）
缺点：
- 当数据分布不均匀时，效率降低
- 需要额外的空间
- 桶的数量和大小需要提前确定，不容易把握
桶排序的优化
- 动态调整桶的数量：根据数据分布特点，动态调整桶的数量和大小
- 结合其他排序算法：对于小数据量的桶，可以使用插入排序；对于大数据量的桶，可以使用快速排序
- 并行处理：不同的桶可以并行排序，提高效率