一、计数排序简介
计数排序是一种非比较排序算法，适用于整数数组，时间复杂度为O(n+k)，其中n为待排序数组的长度，k为待排序数组中最大值与最小值之差。
计算排序的原理是通过计算每个元素的出现次数或位置，而不是通过比较元素之间的大小来进行排序
注意！！！计数排序只适用于整数排序，当数据范围过大时，需要消耗大量的内存空间。
二、Python代码实现
# -*- coding: utf-8 -*-
"""
======================================
File Name ： counting_sort.py
Author ： lanmingyong(小黑测试员)
date ： 2024/6/20 19:44
Description： 计数排序是一种非比较排序算法，适用于整数数组，时间复杂度为O(n)。
计算排序的原理是通过计算每个元素的出现次数或位置，而不是通过比较元素之间的大小来进行排序
注意！！！计数排序只适用于整数排序，当数据范围过大时，需要消耗大量的内存空间。
=======================================
"""
def counting_sort(arr):
min_num = min(arr)
max_num = max(arr)
keys = [str(x) for x in range(min_num, max_num + 1)]
values = [0] * len(keys)
my_dict = dict(zip(keys, values))
new_list = []
# 计数数值出现的次数
for i in arr:
my_dict[str(i)] = my_dict[str(i)] + 1
for key, value in my_dict.items():
if value == 0:
continue
new_list = new_list + [int(key)] * value
return new_list
#验证
# arr = [9, 6, 7, 2, 8, 1, 0, 4, 3, 0]
arr = [89, 65, 21, 8, 76, 79, 0, 86, 51, 33, 34, 8, 76, 53, 93, 88, 65, 0, 92, 56, 76, 9, 0, 54, 9, 37, 94, 72, 92, 72, 88, 44, 34, 48, 14, 22, 76, 34, 45, 50, 66, 4, 77, 41, 64, 24, 65, 99, 16, 64]
if __name__ == '__main__':
print(counting_sort(arr))
#执行输出
"""
[0, 0, 0, 4, 8, 8, 9, 9, 14, 16, 21, 22, 24, 33, 34, 34, 34, 37, 41, 44, 45, 48, 50, 51, 53, 54, 56, 64, 64, 65, 65, 65, 66, 72, 72, 76, 76, 76, 76, 77, 79, 86, 88, 88, 89, 92, 92, 93, 94, 99]
"""注：如果代码有错误欢迎指出交流，感谢！！
三、动画演示
欢迎大家关注我的订阅号，会不定期分享一些相关的文章，有问题也欢迎一起讨论交流学习！