视频字幕
计数排序是一种非比较排序算法，特别适用于对一定范围内的整数进行排序。它的基本思想是统计数组中每个元素出现的次数，然后根据这些统计信息将元素放到正确的位置上。让我们通过一个例子来理解计数排序的工作原理。
计数排序的前两个步骤是确定范围和创建计数数组。首先，我们需要找到输入数组中的最小值和最大值。在这个例子中，最小值是1，最大值是8。然后，我们创建一个计数数组，其大小等于最大值减去最小值加1，也就是8个位置，对应数值1到8。初始时，计数数组的所有元素都设为0。
第三步是统计频率。我们遍历原始数组，统计每个元素出现的次数，并将结果存储在计数数组的对应位置。例如，元素1出现1次，所以计数数组索引1的位置值为1；元素2出现2次，所以计数数组索引2的位置值为2；元素3也出现2次，元素4出现1次，元素8出现1次。这样我们就完成了频率统计。
第四步是修改计数数组，通过累加使每个位置存储小于等于该元素的个数。第五步是填充输出数组，从后向前遍历原数组，根据累加后的计数数组确定每个元素在输出数组中的正确位置。这样可以保证排序的稳定性，相等元素的相对顺序保持不变。最终我们得到排序后的数组。
计数排序是一种高效的非比较排序算法，时间复杂度为O(n+k)，其中n是元素个数，k是元素的取值范围。它的空间复杂度为O(k)，是稳定的排序算法。计数排序适用于元素范围有限且已知的情况，特别是当k相对较小时效率很高。在C++中，我们通常使用vector来实现计数数组，需要注意数组边界和索引映射的处理。