跳转至

计数排序#
发布于2020-11-26
上次编辑2021-02-25 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def counting_sort(nums: List[int]) -> List[int]:
    """计数排序"""

    min_val, max_val = min(nums), max(nums)
    count = [0] * (max_val - min_val + 1)

    for x in nums:
        count[x - min_val] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    nums_sorted = [0] * len(nums)

    # 从后往前遍历是为了保持排序的稳定性
    for x in nums[::-1]:
        count[x - min_val] -= 1
        nums_sorted[count[x - min_val]] = x

    return nums_sorted

  1. 计数排序 ↩

返回顶部

在手机上阅读