PythonRadix排序

我正在尝试在python中实现Radix排序.

我当前的程序工作不正常,因为像[41,51,2,3,123]这样的列表将正确排序到[2,3,41,51,123],但类似于[52,41,51,42,23]将成为[23,41,42,52,51](52和51在错误的地方).

我想我知道为什么会这样,因为当我比较十位的数字时,我也不比较单位(对于10的更高权力也是如此).

如何解决此问题,以便我的程序以最快的方式运行？谢谢！

def radixsort(aList):
BASEMOD = 10
terminateLoop = False
temp = 0
power = 0
newList = []
while not terminateLoop:
terminateLoop = True
tempnums = [[] for x in range(BASEMOD)]
for x in aList:
temp = int(x / (BASEMOD ** power))
tempnums[temp % BASEMOD].append(x)
if terminateLoop:terminateLoop = False
for y in tempnums:
for x in range(len(y)):if int(y[x] / (BASEMOD ** (power+1))) == 0: newList.append(y[x]) aList.remove(y[x])
power += 1
return newList
print(radixsort([1,4,1,5,5,6,12,52,1,5,51,2,21,415,12,51,2,51,2]))


解决方法:

目前,您的排序不会根据除最高位数之外的任何值重新排序值.你只有偶然得到41和42(因为它们在初始列表中的顺序是正确的).

您应该始终根据排序的每个周期构建一个新列表.

def radix_sort(nums, base=10):
result_list = []
power = 0
while nums:
bins = [[] for _ in range(base)]
for x in nums:
bins[x // base**power % base].append(x)
nums = []
for bin in bins:
for x in bin:if x power += 1
return result_list


请注意,基数排序不一定比基于比较的排序更快.如果要排序的项目数大于项目值的范围,则其复杂度较低.它的复杂性是O(len(nums)* log(max(nums)))而不是O(len(nums)* log(len(nums))).