计数排序原理与Python实现

计数排序算法详解1. 算法概述计数排序Counting Sort是一种非比较型的整数排序算法它通过统计每个元素出现的次数来实现排序。与基于比较的排序算法如快速排序、归并排序不同计数排序不涉及元素之间的直接比较而是利用额外的数组空间来统计元素的分布情况。核心特点适用场景数据量大但数据范围较小的整数排序时间复杂度O(n k)其中n是元素个数k是数据范围空间复杂度O(k)稳定性稳定的排序算法2. 算法原理2.1 基本思想计数排序的核心思想是对于给定的输入序列中的每一个元素x确定该序列中值小于x的元素的个数。利用这一信息就可以将x直接存放到最终的输出序列的正确位置上。2.2 算法步骤下面通过表格形式展示计数排序的具体步骤步骤描述目的1找出待排序数组中的最大值和最小值确定计数数组的大小2创建计数数组统计每个元素出现的次数建立元素与频次的映射关系3对计数数组进行累加操作确定每个元素在输出数组中的最终位置4反向遍历原数组根据计数数组放置元素保证排序的稳定性5将输出数组复制回原数组完成排序3. Python代码实现def counting_sort(arr): 计数排序算法的Python实现 参数: arr: 待排序的整数列表 返回: 排序后的整数列表 if len(arr) 0: return arr # 步骤1找出数组中的最大值和最小值 max_val max(arr) min_val min(arr) # 计算数据范围 range_of_elements max_val - min_val 1 # 步骤2创建计数数组并初始化为0 count_arr [0] * range_of_elements output_arr [0] * len(arr) # 统计每个元素出现的次数 for num in arr: count_arr[num - min_val] 1 print(f计数数组: {count_arr}) # 调试信息 # 步骤3对计数数组进行累加 for i in range(1, len(count_arr)): count_arr[i] count_arr[i - 1] print(f累加后的计数数组: {count_arr}) # 调试信息 # 步骤4反向遍历原数组放置元素到正确位置 for i in range(len(arr) - 1, -1, -1): current_num arr[i] position count_arr[current_num - min_val] - 1 output_arr[position] current_num count_arr[current_num - min_val] - 1 # 步骤5将排序结果复制回原数组 for i in range(len(arr)): arr[i] output_arr[i] return arr # 测试示例 if __name__ __main__: # 测试用例1普通情况 test_arr1 [4, 2, 2, 8, 3, 3, 1] print(原始数组:, test_arr1) sorted_arr1 counting_sort(test_arr1.copy()) print(排序结果:, sorted_arr1) print() # 测试用例2包含负数的情况 test_arr2 [-1, 5, -3, 2, 0, -1, 5] print(原始数组:, test_arr2) sorted_arr2 counting_sort(test_arr2.copy()) print(排序结果:, sorted_arr2)4. 算法动图演示原理由于无法直接嵌入动图我将用文字描述计数排序的动态执行过程4.1 初始化阶段原始数组: [4, 2, 2, 8, 3, 3, 1] 最小值: 1, 最大值: 8 数据范围: 8 - 1 1 8 计数数组初始: [0, 0, 0, 0, 0, 0, 0, 0]4.2 统计频次阶段遍历原数组统计每个数字出现的次数遇到1 → 计数数组索引0加1遇到2 → 计数数组索引1加1出现两次遇到3 → 计数数组索引2加1出现两次遇到4 → 计数数组索引3加1遇到8 → 计数数组索引7加1最终计数数组[1, 2, 2, 1, 0, 0, 0, 1]4.3 累加计数阶段将计数数组转换为位置信息原始计数: [1, 2, 2, 1, 0, 0, 0, 1] 累加后: [1, 3, 5, 6, 6, 6, 6, 7]这表示数字1应该放在位置0-0实际位置0数字2应该放在位置1-2实际位置1-2数字3应该放在位置3-4实际位置3-4数字4应该放在位置5实际位置5数字8应该放在位置6实际位置64.4 反向填充阶段从原数组末尾开始反向遍历最后一个元素1 → 放到输出数组位置0元素3 → 放到输出数组位置4元素3 → 放到输出数组位置3元素8 → 放到输出数组位置6元素2 → 放到输出数组位置2元素2 → 放到输出数组位置1元素4 → 放到输出数组位置5最终得到排序结果[1, 2, 2, 3, 3, 4, 8]5. 算法性能分析5.1 时间复杂度计数排序的时间复杂度分析如下操作时间复杂度说明寻找最大值最小值O(n)需要遍历整个数组创建计数数组O(k)k为数据范围大小统计元素频次O(n)遍历原数组一次累加计数数组O(k)遍历计数数组一次反向填充O(n)再次遍历原数组总时间复杂度O(n k)当kO(n)时为线性时间复杂度5.2 空间复杂度计数排序需要额外的空间计数数组O(k)输出数组O(n)总空间复杂度O(n k)5.3 稳定性分析计数排序是稳定的排序算法。在反向填充阶段从原数组末尾开始遍历保证了相同元素的相对顺序不变。这种稳定性在某些应用场景中非常重要比如需要保持原始数据中相同值的相对位置。6. 适用场景与限制6.1 适用场景计数排序在以下场景中表现优异数据范围较小当k数据范围远小于n数据量时整数排序只能用于整数排序因为需要将元素作为数组索引稳定性要求需要稳定排序的场景小范围数据如年龄排序、成绩排序等6.2 局限性数据类型限制只能用于整数排序空间消耗当数据范围很大时空间复杂度较高负数处理需要额外处理负数情况通过偏移量非均匀分布如果数据分布不均匀会造成空间浪费7. 优化版本针对数据范围较大的情况可以使用以下优化def optimized_counting_sort(arr): 优化版的计数排序处理大数据范围情况 if len(arr) 1: return arr # 使用字典代替数组节省空间 count_dict {} # 统计频次 for num in arr: count_dict[num] count_dict.get(num, 0) 1 # 获取排序后的键 sorted_keys sorted(count_dict.keys()) # 构建结果 result [] for key in sorted_keys: result.extend([key] * count_dict[key]) return result # 测试优化版本 test_arr [10, 3, 7, 3, 2, 10, 7, 2, 3] print(优化前数组:, test_arr) print(优化后结果:, optimized_counting_sort(test_arr))8. 与其他排序算法对比计数排序在特定场景下比其他排序算法更有优势排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性适用场景计数排序O(n k)O(n k)O(n k)O(n k)稳定小范围整数快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定通用场景归并排序O(n log n)O(n log n)O(n log n)O(n)稳定大数据量堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定原地排序计数排序通过牺牲空间来换取时间效率在数据范围较小的情况下能够达到线性时间复杂度这是基于比较的排序算法无法实现的。参考来源10-算法-基数排序一文总结十大经典排序算法思维导图 动图演示 代码实现 C/C/Python 致命吐槽【数据结构】排序算法---计数排序动图演示10 大经典排序算法 Python 版实现附动图演示Python实现计数排序常见十大排序算法动图演示Python3实现