python实现【计数排序】(CountSort)

算法原理及介绍

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，将数组的索引当做每一个元素，然后统计每个索引即元素出现的次数记录在该所索引位置处。如：nums[i]=j:表示数值i在序列中出现的次数为j。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法过程描述

1. 找出待排序的数组中最大和最小的元素；

2. 统计数组中每个值为i的元素出现的次数，存入count_nums数组的第i项；

3. 将count_nums数组中从左向右每一个计数不为0的值依次填充进最终的res排序数组中。

算法排序图解如下

计数排序.gif

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

如果喜欢作者，欢迎点赞、收藏及关注，谢谢！
点击下面相应的链接即可查看各个算法的详细介绍及python实现方法：

1. 冒泡排序(BubbleSort)
2. 选择排序(SelectionSort)
3. 插入排序(InsertSort)
4. 归并排序(MergeSort)
5. 快速排序(QuickSort)
6. 堆排序(Heap Sort)
7. 计数排序(Count Sort)
8. 桶排序(Bucket Sort)
9. 基数排序(Radix Sort)
10. 希尔排序(Shell Sort)