基数排序

一、原理

• 先取数组中最大元素的位深(个、十、百...)。
• 按个位分桶，然后取出。
• 按十位分桶，然后取出。
• 依次类推...

二、代码实现

import numpy as np
from time import time

# 基数排序
def radix_sort(arr):
    # 先取数组中的最大元素的位深
    max_num_len = len(str(max(arr)))
    index = 0
    while index < max_num_len:
        # 初始化桶
        bucket_list = [[] for _ in range(10)]
        # 将元素分别放入对应的桶中
        for x in arr:
            # (a // 10 ** index) % 10
            temp = (x // 10 ** index) % 10
            bucket_list[temp].append(x)
        # 将桶中的元素按顺序放入arr中
        arr.clear()
        for l in bucket_list:
            arr.extend(l)
        index += 1


if __name__ == "__main__":
    # 基数排序
    np.random.seed(10)
    array = list(np.random.randint(0, 100, size=(30,)))
    print("排序前：", array)
    start = time()
    radix_sort(array)
    print("排序后：", array)
    end = time()
    print(f"radix_sort()函数耗时{end - start}秒")
    print(array[:100])

运行结果：