基数排序
(1) 基数排序思路
基数排序 (Radix Sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序法会使用到桶 (Bucket)，顾名思义，通过将要比较的位（个位、十位、百位…），将要排序的元素分配至 0~9 个桶中，借以达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
从最低位开始，依次进行一次排序
从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
(2) 举几个小例子
例1: 将一个数字例如345, 随意取出任何一个位数的数字1
2
3def get_digit(nums, i):
# i=0 取个位数 i=1 取十位数 ...
return num // (10**i) % 10
例2: 将一个数字一一存入列表中,例如num=12345 -> [1,2,3,4,5]1
2
3
4
5
6
7def int_to_list(num):
li = []
while num > 0:
li.append(num % 10)
num = num //10
li.reverse()
return li
或者可以自己写reverse方法1
2
3
4def reverse_list(li):
for i in range(len(li) // 2):
li[i], li[n-i-1] = li[n-i-1], li[i]
return li
扩展:实现将数字123->321 12300->321 -12300->-3211
2
3
4
5
6
7
8
9
10
11
12
13
14
15def reverse_int(num):
is_neg = False
res = 0
if num < 0:
is_neg = True
num = num * -1
while num > 0:
res = res * 10
res += num % 10
num = num // 10
if is_neg:
res = res * -1
return res
(3) 基数排序代码实现:
1 | def radix_sort(li): |