作为一名对技术充满热情的学习者，我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代，我远非专家，而是一位不断追求进步的旅行者。通过这篇博客，我想分享我在某个领域的学习经验，与大家共同探讨、共同成长。请大家以开放的心态阅读，相信你们也会在这段知识之旅中找到启示。
前言
关于计数排序，我们在考研中或者平时练习中还是比较难以见到的，但在工作中，我们还是必须要学会正确使用。
一、什么是计数排序
计数排序（Counting Sort）是一种非比较型的线性时间复杂度的排序算法，最适合于一定范围内的整数排序问题。它是一个整数排序算法，且只能用在待排序元素的值是有限范围的情况下。
计数排序工作原理：
- 扫描待排序数组，假设数组中有n个数，并找出数组中的最大值max。
- 开辟一个长度为max+1的计数数组，以记录每个值为i的元素出现的次数，初始化为0。
- 再次扫描原始数组，对于数组中的每个数值，将计数数组对应数值的计数加一。
- 现在，对计数数组进行“累加”，累加的结果表示了值为i的元素在最终排序数组中的最后一个位置的索引加1。
- 最后，反向填充目标数组：遍历原数组，对于每个元素，查找其值在计数数组中对应的索引，这个索引就是该元素在输出数组中的位置（因为做了累加，所以计数时该位置可能是该元素的最后一个可能位置），每放一个元素就将计数减一。
计数排序算法的代码如下（以Java为例）：
public static void countingSort(int[] array) { // 找出数组A中的最大值 int maxVal = array[0]; for (int i : array) { if (i > maxVal) maxVal = i; } // 初始化计数数组count，长度为maxVal+1 int[] count = new int[maxVal + 1]; // 对每个数出现的次数进行计数 for (int i : array) { count[i]++; } // 对所有的计数累加 for (int i = 1; i < count.length; i++) { count[i] += count[i - 1]; } // 反向填充目标数组 int[] sorted = new int[array.length]; for (int i = array.length - 1; i >= 0; i--) { sorted[--count[array[i]]] = array[i]; } // 将排序后的数组元素复制回原数组 System.arraycopy(sorted, 0, array, 0, array.length); }
计数排序的时间复杂度是O(n+k)，其中n是数组长度，k是正整数的取值范围。它的空间复杂度是O(k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
计数排序的优点是：
- 线性的时间复杂度，非常高效。
- 尤其适合于数据范围不大的场合。
计数排序的缺点包括：
- 当数值的最大和最小值差距过大时，并不适合使用计数排序。
- 只能用于整数排序，而且必须是非负整数。
- 如果元素不能转换为有效的索引，如负数或浮点数，或元素范围太大导致无法开辟那么多空间，也不适合使用计数排序。
二、计数排序适用于什么样的数据范围
计数排序特别适合于以下数据范围的场景：
- 数据范围有限且值是非负整数：计数排序要求输入数据是有确定范围的整数。最理想的数据范围是数值不是太大的非负整数，因为算法需要创建一个长度等于输入数据中的最大值加一的计数数组。
- 离散型数据：由于计数排序是通过直接计算每个数值的出现次数来排序的，因此它非常适合离散型数据，如学生成绩（0-100分）、年龄分布（按年龄分组）、少量字符的ASCII码等。
- 数据量较大且数据密集：计数排序的时间效率很高，尤其是当数据量很大而且值的范围并不宽广时，比传统比较排序要高效得多。
- 线性时间要求：当需要一个稳定的线性时间排序算法时，如果数据符合上述条件，计数排序是一个非常好的选择。
适用性限制：
- 如果数值最大和最小之差过大，即使数据的实际分布可能很紧密，计数排序也可能因为需要创建过大的计数数组而变得不实际。
- 对于含有负数的数组，需要先将数据进行转换，比如说统一加上一个偏移量，转换为全正的数组后排序，排序完成后再转换回去。
- 对于非整数数据，比如字符串或浮点数，计数排序无法直接应用，除非它们能够有效地转换成整数且值的范围有限。
- 计数排序是稳定的排序算法，在含有重复元素的数组中，可以保持它们原有的顺序。
三、简单练习
当然可以。下面，我将通过一个简单的例子演示如何对一个整数数组利用计数排序进行排序。假设我们有以下这个整数数组：
[4, 2, 2, 8, 3, 3, 1]
我们想要按照从小到大的顺序对它进行排序。计数排序的步骤如下：
- 找出数组中的最大值（在这个例子中为8）和最小值（在这个例子中为1），确定计数数组的大小。
- 初始化计数数组，计数每个整数在原始数据中出现的次数。
- 累加计数数组，使得每个元素的数值表示原数组中相应整数及其比它小的整数的总数。
- 反向遍历原始数组，根据计数数组中的数值将每个整数放到排序后数组的正确位置。
- 将排序后的数组返回。
在Java中的具体实现如下：
public class CountingSortExample { public static void main(String[] args) { int[] array = {4, 2, 2, 8, 3, 3, 1}; // 输入数组 countingSort(array); // 调用计数排序函数 for (int i : array) { System.out.print(i + " "); // 输出排序结果 } } public static void countingSort(int[] array) { int max = array[0], min = array[0]; // 找到数组中的最大最小值 for (int i = 1; i < array.length; i++) { if (array[i] > max) max = array[i]; if (array[i] < min) min = array[i]; } // 初始化计数数组，范围[min, max] int[] count = new int[max - min + 1]; // 计数各个数字的出现次数 for (int value : array) { count[value - min]++; } // 重写原始数组，用于输出排序结果 int index = 0; for (int i = 0; i < count.length; i++) { while (count[i] > 0) { array[index++] = i + min; count[i]--; } } } }
当该代码执行完毕后打印出来的数组应该是排序后的结果：
1 2 2 3 3 4 8
这样，原始数组就通过计数排序算法被排序好了。需要注意的是，因为计数排序是根据数值的范围来计数的，所以它尤其适合于数值范围并不是很广的场合。在这个例子中，原数组中的数值范围是1到8，是比较适合使用计数排序的。
四、Java面试题
面试题：
给定一组非负整数代表的颜色编码，其中每个颜色编码相同代表相同颜色的小球，现在要求你通过一次遍历完成颜色小球的排序。已知颜色种类的范围很有限（例如0到K-1），请你实现一个排序算法来解决这个问题，并说明你的算法的时间复杂度和空间复杂度。
详细解释：
这个问题本质上是要求实现一个计数排序算法的变体，因为小球颜色的种类有限，完全可以利用计数排序算法来解决。这题的难点在于要求一次遍历，所以传统的计数排序需要稍作调整，我们可以在统计阶段同时完成排序工作，这种方法也称为"一次遍历的计数排序"（One-Pass Counting Sort）。
算法步骤：
- 首先，创建一个额外的数组count，用于计数，其长度等于颜色编码的种类数K。
- 遍历颜色编码数组，每读到一个颜色编码，就在count数组相应的颜色编码位置上加1，同时，按照目前的计数，将颜色编码放置在排序数组中的合适位置。这步是算法的关键，需要通过累加的计数来定位颜色编码在排序数组中的位置。
- 最终，当遍历完一遍之后，排序完成。
Java实现：
public class OnePassCountingSort { public static void sortColors(int[] colors) { int[] count = new int[K]; // 假设K是颜色编码的种类数 int[] output = new int[colors.length]; // 输出的排序数组 // 一次遍历，计数并排序 for (int i = 0; i < colors.length; i++) { count[colors[i]]++; int pos = 0; for (int j = 0; j < colors[i]; j++) { pos += count[j]; // 得到当前颜色编码应放置的位置 } output[pos + count[colors[i]] - 1] = colors[i]; } // 复制回原数组（如果需要） System.arraycopy(output, 0, colors, 0, colors.length); } public static void main(String[] args) { int[] colors = {2, 1, 1, 0, 2, 1, 0}; // 示例颜色编码数组 sortColors(colors); for (int color : colors) { System.out.print(color + " "); } } }
时间复杂度和空间复杂度：
- 时间复杂度：O(n+k)，其中n是颜色编码数组的大小，k是颜色种类数。在这里，遍历数组的时间复杂度为O(n)，统计颜色编码的时间复杂度为O(k)，总体上仍然是线性复杂度。
- 空间复杂度：O(k)，只需要创建一个大小为k的计数数组。
这种一次遍历的计数排序方式虽然符合题目要求，但在实际应用中可能会因为在内层循环中遍历计数数组而导致效率不如传统计数排序。通常情况下，传统的两遍遍历计数排序因其简单高效而更为流行。
思考计数排序算法中的累加计数的作用
计数排序算法中的累加计数步骤起着非常关键的作用，它是算法能够稳定排序和确定元素排名位置的基础。
在计数排序中，累加计数步骤之前，我们通常会创建一个计数数组，用来记录每个元素在原始数组中的出现次数。如果原始数组中的元素是一系列非负整数，那么这些整数的值就可以直接作为计数数组的索引，其对应的计数数组的值就是该索引元素在原始数组中的出现次数。
累加计数是在完成基本的计数之后进行的操作，具体步骤如下：
- 对计数数组进行遍历，从第一个元素开始。
- 将当前的计数数组元素值加上前一个元素的值，然后将结果写回当前元素的位置上。
- 重复步骤2，直到遍历完整个计数数组。
在这个过程中，每个元素的值变为了原数组中所有小于等于该元素的个数之和。这就意味着，累加之后的计数数组中的每个位置i的值，都是原始数组中小于等于i值的元素个数。
为什么这个步骤是必要的？关键点在于它让我们能够确定每个元素在排序后的数组中的位置。具体来说：
- 值i在排序后数组中的终止位置就是计数数组中i的值减一（因为数组是从0开始计数的）。
- 如果有多个相同的元素i，每放置一个元素，计数数组中i的值就减少一，这保证了相同元素能够正确连续放置，并且保持了它们在原数组中的顺序（稳定性）。
例如，考虑原始数组[4, 2, 2, 8, 3, 3, 1]的计数数组[1, 2, 2, 1, 0, 0, 0, 1]（假设有8种可能的元素值，从1到8）。经过累加计数后，计数数组变为[1, 3, 5, 6, 6, 6, 6, 7]。这意味着：
- 值1之前没有其他元素，也就是它应该在排序数组的第一个位置。
- 值2之前有一个1，所以2从排序数组的第2个位置开始。
- 值8之前有6个元素（1, 2, 2, 3, 3, 4），所以8在排序数组的第7个位置。
因此，累加计数不仅帮助确定了每个元素的最终位置，也使得计数排序成为了一个稳定的排序算法。
总结
计数排序是一种高效的线性时间排序算法，特别适用于有限范围的整数数据。它利用一个额外的计数数组来记录待排序数组中每个元素的出现频次，通过累加计数来确定每个元素在输出数组中的位置。由于其稳定性和线性时间复杂度（即O(n+k)，其中n是原数组的元素个数，k是数值范围），计数排序成为了处理大量离散且具有小范围数值数据的理想选择。然而，需要注意的是，计数排序在处理大范围或者数据量大小远超数值范围时，会变得不那么高效，因此它的使用场景相对受限。总的来说，计数排序是一种对于特定数据集合而言非常实用的排序方法。
感谢大家抽出宝贵的时间来阅读博主的博客,新人博主,感谢大家关注点赞,祝大家未来的学习工作生活一帆风顺,加油!!!
