基数排序基数排序

一、原理

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

文章图片
二、代码实现

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 += 1if __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])

【基数排序】运行结果：