1. 概述
在本篇文章中，我们将探讨如何高效地对一个包含小整数的数组进行排序。我们会先明确问题定义，然后通过一个示例进行说明。最后，我们介绍两种适用场景：一种是针对小整数数组的排序，另一种是适用于数组中任意两个元素之间绝对差值较小的情况。
这篇文章的核心是 计数排序（Counting Sort） 及其变种，它非常适合在已知数值范围较小的前提下进行排序，时间复杂度优于通用排序算法（如快速排序、归并排序等）。
2. 问题定义
假设我们有一个整数数组 A，包含 N 个较小的整数值。我们的目标是尽可能高效地将它排序。
举个例子：
给定数组 A = [2, 5, 1, 4, 3]，我们希望将其重新排列为 A = [1, 2, 3, 4, 5]。
也就是说，我们希望数组满足如下条件：
A[i] ≥ A[i - 1]，其中 i 的取值范围是 1 ≤ i < N。
这个排序问题是一个特殊场景下的排序问题。由于数组中的值较小，我们可以利用这一点来选择更高效的排序算法。
3. 计数排序方法
3.1 核心思想
✅ 核心思想：统计每个数字出现的次数，然后按从小到大的顺序将它们依次写入新数组中。
具体来说：
- 遍历原始数组 A，统计每个数字的出现次数；
- 然后从 0 到最大值依次遍历，将每个数字按照其出现次数依次写入结果数组；
- 最终得到的数组就是排序后的结果。
这个方法非常适合小整数数组，因为我们可以用一个固定大小的数组来统计频率，而无需使用哈希表等复杂结构。
3.2 实现代码
public static int[] countingSort(int[] A) {
if (A == null || A.length == 0) return new int[0];
int max = Arrays.stream(A).max().getAsInt();
int[] count = new int[max + 1];
// Step 1: 统计每个数字出现的次数
for (int num : A) {
count[num]++;
}
// Step 2: 生成排序后的数组
int[] sorted = new int[A.length];
int idx = 0;
for (int i = 0; i <= max; i++) {
while (count[i]-- > 0) {
sorted[idx++] = i;
}
}
return sorted;
}
3.3 时间复杂度分析
✅ **时间复杂度：O(N + M)**，其中：
- N 是数组 A 的长度；
- M 是数组中最大值。
⚠️ 注意： 如果数组中最大值非常大（比如 10^6），那么这种方法会占用大量内存，效率反而会下降。所以它只适用于数值范围较小的数组。
4. 小绝对差值情况下的排序方法
4.1 核心思想
✅ 核心思想：通过偏移量将所有元素调整为非负数，从而缩小计数数组的大小。
当数组中元素之间的绝对差值较小时，我们可以：
- 找出数组中的最小值作为偏移量 offset；
- 将每个元素减去 offset，变成非负数；
- 使用计数排序对这些偏移后的值进行排序；
- 最后加上 offset，还原为原始值。
这样做的好处是：我们不需要为非常大的最大值分配额外空间。
4.2 实现代码
public static int[] countingSortWithSmallAbsoluteDifference(int[] A) {
if (A == null || A.length == 0) return new int[0];
int min = Arrays.stream(A).min().getAsInt();
int max = Arrays.stream(A).max().getAsInt();
int range = max - min + 1;
int[] count = new int[range];
// Step 1: 偏移后统计频率
for (int num : A) {
count[num - min]++;
}
// Step 2: 生成排序后的数组
int[] sorted = new int[A.length];
int idx = 0;
for (int i = 0; i < range; i++) {
while (count[i]-- > 0) {
sorted[idx++] = i + min;
}
}
return sorted;
}
4.3 时间复杂度分析
✅ **时间复杂度：O(N + D)**，其中：
- N 是数组 A 的长度；
- D 是数组中最大值与最小值的差值（即 max(A) - min(A)）。
⚠️ 注意： 如果 D 很小，比如几十或几百，这个方法非常高效。即使数组中存在负数，也可以通过偏移量处理，不影响排序效率。
5. 总结
本文我们介绍了两种适用于小整数数组的排序方法：
✅ 计数排序（Counting Sort）：
- 适合数组元素值较小的情况；
- 时间复杂度 O(N + M)，其中 M 是最大值；
- 缺点是不能处理大范围数值。
✅ 带偏移量的计数排序（Offset Counting Sort）：
- 适合数组中任意两个元素的绝对差值较小的情况；
- 时间复杂度 O(N + D)，其中 D 是最大值与最小值之差；
- 可以处理负数。
这两种方法都比通用排序算法（如快速排序、归并排序）在特定场景下更快，尤其适合数据范围有限的整数数组排序。
如果你在实际项目中遇到这类问题，可以优先考虑使用这些方法，能显著提升性能。