- 首页 > it技术 > >
Radix|Radix Sort. Θ(d(n+k)) => Θ(numOfDigits*(amount+scope))
from random import choicesdef countingSort(source:[], digits:[], scope:int) -> []:
counter = [0]*scope
amount = len(source)for x in digits:
counter[x] += 1for i in range(1, scope):
counter[i] += counter[i-1]destination = [0]*amountfor i in reversed(range(amount)):
quantity = digits[i]
# index = count-1
destination[counter[quantity]-1] = source[i]
counter[quantity] -= 1return destinationscope = 10
amount = 1000
numOfDigits = 3
source = choices(range(amount), k=amount)for i in range(numOfDigits):
digits = []
for x in source:
temp = x // (scope ** i)
digit = temp % scope
digits.append(digit)source = countingSort(source, digits, scope)
推荐阅读
