中央广播电视总台简称_ui一般用什么软件做_app注册接单平台_百度站长平台网站收录

计数排序（counting sort）通过统计元素数量来实现排序，通常应用于整数数组。
给定一个长度为 的数组 nums ，其中的元素都是“非负整数”

def counting_sort(nums: list[int]):"""计数排序"""# 完整实现，可排序对象，并且是稳定排序# 1. 统计数组最大元素 mm = max(nums)# 2. 统计各数字的出现次数# counter[num] 代表 num 的出现次数counter = [0] * (m + 1)for num in nums:counter[num] += 1# 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”# 即 counter[num]-1 是 num 在 res 中最后一次出现的索引for i in range(m):counter[i + 1] += counter[i]# 4. 倒序遍历 nums ，将各元素填入结果数组 res# 初始化数组 res 用于记录结果n = len(nums)res = [0] * nfor i in range(n - 1, -1, -1):num = nums[i]res[counter[num] - 1] = num  # 将 num 放置到对应索引处counter[num] -= 1  # 令前缀和自减 1 ，得到下次放置 num 的索引# 使用结果数组 res 覆盖原数组 numsfor i in range(n):nums[i] = res[i]

计数排序只适用于非负整数。若想将其用于其他类型的数据，需要确保这些数据可以转换为非负整数，并且在转换过程中不能改变各个元素之间的相对大小关系。例如，对于包含负数的整数数组，可以先给所有数字加上一个常数，将全部数字转化为正数，排序完成后再转换回去。