详解计数排序（Counting Sort）

计数排序是一种非比较排序算法，它适用于对一定范围内的整数进行排序。与常见的基于比较的排序算法（如冒泡排序、插入排序、快速排序等）不同，计数排序的基本思想是利用数组下标来确定元素的正确位置。

计数排序的工作原理相对简单直观。需要找出待排序数组中的最大值和最小值，以确定计数数组的范围。然后，创建一个计数数组，其长度为最大值减去最小值加 1，并将其初始化为 0 。接下来，遍历待排序数组，对于每个元素，在计数数组中对应的位置加 1 ，以统计每个元素出现的次数。

完成计数后，通过对计数数组进行累加操作，就可以确定每个元素在排序后的最终位置。最后，根据计数数组中的信息，将待排序数组中的元素放置到正确的位置上，从而得到排序后的数组。

计数排序的优点非常显著。它的时间复杂度为 O(n + k) ，其中 n 是待排序数组的长度， k 是数组中元素的取值范围。在 k 相对较小时，计数排序的效率非常高，甚至比一些高级的排序算法（如快速排序）还要快。计数排序是稳定的排序算法，即相同值的元素在排序前后的相对顺序保持不变。

然而，计数排序也有其局限性。它要求输入的数据必须是一定范围内的整数，并且当 k 较大时，可能需要消耗大量的额外空间来存储计数数组。另外，如果输入的数据范围分布不均匀，计数排序的效率可能会受到影响。

在实际应用中，如果数据的特点符合计数排序的要求，那么选择计数排序可以极大地提高排序的效率。例如，在对学生成绩进行排序（成绩通常在一定的范围内，如 0 - 100 分），或者对一些有限种类的对象进行排序时，计数排序是一个不错的选择。

计数排序是一种简单而高效的排序算法，理解和掌握它对于优化算法性能和解决特定问题具有重要意义。通过合理地运用计数排序，可以在一些特定场景中实现快速、准确的排序操作。