Created
September 14, 2018 05:19
-
-
Save Xifeng2009/6d5f20ddd0e438893798e3a2476281d4 to your computer and use it in GitHub Desktop.
基数排序
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
#encoding=utf-8 | |
import math | |
def sort(a, radix=10): | |
"""a为整数列表, radix为基数""" | |
K = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数 | |
bucket = [[] for i in range(radix)] # 不能用 [[]]*radix | |
for i in range(1, K+1): # K次循环 | |
for val in a: | |
bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整数第K位数字 (从低到高) | |
del a[:] | |
for each in bucket: | |
a.extend(each) # 桶合并 | |
bucket = [[] for i in range(radix)] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment