基数排序-python版
# 基数排序
# 针对非负数排序
class radixSort():
def radixSortAll(self, arr):
"""
对数组arr进行基数排序
:param arr: List[int]
:return: None
"""
if len(arr) < 2:
return
self.radixSortLR(arr, 0, len(arr)-1, self.maxBits(arr))
def maxBits(self, arr):
"""
求数组arr的最大位数
:param arr: List[int]
:return: int
"""
#最大位数记为max_bits
max_bits = 0
#寻找数组中的最大值max_num
max_num = -1
for i in range(len(arr)):
max_num = max(arr[i], max_num)
# 计算最大值的位数
while max_num != 0:
max_bits += 1
max_num //= 10
return max_bits
def radixSortLR(self, arr, L, R, digit):
"""
对数组arr的L~R位置进行基数排序,其中位数最大为digit
:param arr:List[int]
:param L:int
:param R:int
:param digit:int
:return:None
"""
#设置基数
radix = 10
#辅助空间数组
help = [0]*(R-L+1)
#从个位开始,一位一位排序
for i in range(digit):
#统计当前位的词频
count = [0] * radix
for j in range(R-L+1):
cur_num = self.getDigit(arr[L+j], i+1)
count[cur_num] += 1 #此处count[cur_num]的值表示数字cur_num出现的次数
#统计好词频之后,将每个位置代表的次数向后累加
j = 1
while j < len(count):
count[j] += count[j-1] #此时count[j]表示小于等于j的数字出现的次数
j += 1
#从右向左拿出原数组的数按照当前位进行排序
j = R
while j >= L:
current = self.getDigit(arr[j], i+1)
help[count[current]-1] = arr[j]
count[current] -= 1
j -= 1
#本轮排完序的数拷贝回原数组
for j in range(len(help)):
arr[L+j] = help[j]
def getDigit(self, num, d):
"""
获取数字num的第d位数字(从个位开始)
:param num: int
:param d: int
:return: int
"""
for i in range(d):
res_num = num % 10
num = num // 10
return res_num
标签:count,arr,python,max,左神,int,算法,num,param
From: https://www.cnblogs.com/ljdsbfj/p/16585425.html