计数排序（Counting Sort） 计数排序是一种非比较型的整数排序算法，特别适用于待排序元素的范围（最大值与最小值之间的差值）不大但数量很多的情况。它的核心思想是通过统计每个整数出现的次数，然后直接计算出每个元素在排序后数组中的位置。 基本思想与适用条件 要求输入数据必须是整数，并且范围已知（或可通过遍历确定） 时间复杂度为O(n+k)，其中n是元素个数，k是整数范围大小 当k=O(n)时，算法效率很高；但当k远大于n时，空间浪费严重 算法步骤详解 步骤1：确定范围 首先遍历整个数组，找出最大值max和最小值min，计算范围大小k = max - min + 1 示例：数组[ 4,2,2,8,3,3,1 ] min = 1, max = 8 k = 8 - 1 + 1 = 8 步骤2：创建计数数组 创建一个长度为k的计数数组count，初始值全为0 count[ i ]将用于存储数值(min+i)出现的次数 示例：count数组长度为8，索引0对应数值1，索引7对应数值8 步骤3：统计出现次数 遍历原数组，对于每个元素x，计算其在计数数组中的索引：index = x - min 然后将count[ index ]的值加1 示例统计过程： 元素4：index = 4-1 = 3 → count[ 3 ]++ 元素2：index = 2-1 = 1 → count[ 1 ]++ 元素2：index = 1 → count[ 1 ]++ 元素8：index = 8-1 = 7 → count[ 7 ]++ 元素3：index = 3-1 = 2 → count[ 2 ]++ 元素3：index = 2 → count[ 2 ]++ 元素1：index = 1-1 = 0 → count[ 0 ]++ 最终count数组：[ 1,2,2,1,0,0,0,1 ] 表示：数值1出现1次，数值2出现2次，数值3出现2次，数值4出现1次，数值8出现1次 步骤4：计算累积频次（关键步骤） 将计数数组转换为累积频次数组，使得count[ i ]表示小于等于(min+i)的元素总数 方法：从索引1开始，将每个count[ i]加上前一个count[ i-1 ] 计算过程： count[ 0 ] = 1（保持不变） count[ 1 ] = 1+2 = 3 count[ 2 ] = 3+2 = 5 count[ 3 ] = 5+1 = 6 count[ 4 ] = 6+0 = 6 count[ 5 ] = 6+0 = 6 count[ 6 ] = 6+0 = 6 count[ 7 ] = 6+1 = 7 累积频次数组：[ 1,3,5,6,6,6,6,7 ] 含义：≤1的元素有1个，≤2的有3个，≤3的有5个，≤4的有6个，≤8的有7个 步骤5：反向填充结果数组 创建一个与原数组等长的结果数组 从原数组末尾向前遍历（保证稳定性）： 对于每个元素x，计算index = x - min 在结果数组中，该元素的位置应该是count[ index ] - 1 将x放入结果数组的该位置，然后将count[ index ]减1 填充过程（从原数组末尾开始）： 元素1：index=0，位置=count[ 0]-1=1-1=0 → 结果[ 0]=1，count[ 0 ]=0 元素3：index=2，位置=count[ 2]-1=5-1=4 → 结果[ 4]=3，count[ 2 ]=4 元素3：index=2，位置=4-1=3 → 结果[ 3]=3，count[ 2 ]=3 元素8：index=7，位置=count[ 7]-1=7-1=6 → 结果[ 6]=8，count[ 7 ]=6 元素2：index=1，位置=count[ 1]-1=3-1=2 → 结果[ 2]=2，count[ 1 ]=2 元素2：index=1，位置=2-1=1 → 结果[ 1]=2，count[ 1 ]=1 元素4：index=3，位置=count[ 3]-1=6-1=5 → 结果[ 5]=4，count[ 3 ]=5 最终排序结果：[ 1,2,2,3,3,4,8 ] 算法特性分析 稳定性：通过反向填充保证相等元素的相对顺序不变 空间复杂度：O(k)用于计数数组，O(n)用于结果数组，总空间O(n+k) 局限性：仅适用于整数排序，当k很大时效率低下 计数排序是桶排序和基数排序的基础，理解它有助于掌握更复杂的非比较排序算法。