基数排序

发布于2020-11-26

上次编辑2021-02-25

def radix_sort(nums: List[int]) -> None:
    """基数排序"""

    max_val = max(nums)
    key = 1
    while max_val // key:

        # 计数排序
        count = [0] * 10
        for x in nums:
            count[(x // key) % 10] += 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 // key) % 10] -= 1
            nums_sorted[count[(x // key) % 10]] = x

        nums[::] = nums_sorted.copy()

        key *= 10

---

1. 基数排序 ↩

返回顶部

在手机上阅读