python实现【计数排序】(Coun Sort)
算法原理及介绍
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，将数组的索引当做每一个元素，然后统计每个索引即元素出现的次数记录在该所索引位置处。如：nums[i]=j:表示数值i在序列中出现的次数为j。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法过程描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入count_nums数组的第i项；
- 将count_nums数组中从左向右每一个计数不为0的值依次填充进最终的res排序数组中。
算法排序图解如下
python实现代码
def countSort(arr): max_value = max(arr) res = [] count_nums = [0 for i in range(max_value + 1)] for num in arr: count_nums[num] += 1 for i in range(len(count)): if count_nums[i] != 0: # 元素i有 count_nums[i]个，添加入最终的排序数组 res.extend(count_nums[i] * [i]) return res
