计数排序（counting sort）的降序排序实现原理是什么？

核心差异说明 #

计数排序升序、降序的频次统计逻辑完全一致，仅在前缀和计算方向、结果数组填充规则两个环节存在差异，整体时间复杂度仍然保持O(n+k)（n为原数组长度，k为元素取值范围大小），也可以保留排序稳定性。

具体实现步骤 #

步骤1：统计元素出现频次（和升序实现完全相同） #

• 遍历待排序数组，获取数组的最小值min_val、最大值max_val，确定计数数组长度为max_val - min_val + 1
• 初始化全0的计数数组，遍历原数组，元素num对应的计数下标为num - min_val，对应计数项+1，完成所有元素的频次统计

步骤2：反向计算前缀和（和升序的核心差异1） #

升序实现是从左到右（对应元素从小到大）计算前缀和，得到的是「小于等于当前值的元素总个数」，用来确定元素在升序数组的最终位置。
降序实现需要从右到左（对应元素从大到小）计算前缀和，得到的是「大于等于当前值的元素总个数」，用来确定元素在降序数组的最终位置。

举个示例：
待排序数组为[2,5,3,5,7]，统计后的计数数组为[1,1,2,1]（对应元素2出现1次、3出现1次、5出现2次、7出现1次）

升序前缀和（从左到右计算）：[1,2,4,5]，代表小于等于5的元素共有4个
降序前缀和（从右到左计算）：[5,4,3,1]，代表大于等于5的元素共有3个

步骤3：填充结果数组（和升序的核心差异2） #

如果需要保证排序稳定性，倒序遍历原数组，用当前元素对应的前缀和减1作为下标，将元素放到结果数组的对应位置，同时将对应计数项减1即可。

代码示例（Python） #

def counting_sort_desc(arr):
    if len(arr) <= 1:
        return arr
    # 1. 统计元素频次
    min_val = min(arr)
    max_val = max(arr)
    count_arr = [0] * (max_val - min_val + 1)
    for num in arr:
        count_arr[num - min_val] += 1
    # 2. 从右到左计算前缀和
    for i in range(len(count_arr)-2, -1, -1):
        count_arr[i] += count_arr[i+1]
    # 3. 倒序遍历原数组填充结果，保证稳定性
    res = [0] * len(arr)
    for num in reversed(arr):
        idx = count_arr[num - min_val] - 1
        res[idx] = num
        count_arr[num - min_val] -= 1
    return res

常见优化说明 #

如果不需要保留排序稳定性，也可以直接遍历计数数组，从大到小按频次把元素塞进结果数组，代码更简洁，但会丢失相同元素的相对位置。

内容的提问来源于stack exchange，提问作者Deepu