Python根

Question

我尝试在python中实现基数排序。在

我当前的程序不能正常工作，因为像[41,51,2,3123]这样的列表将被正确排序到[2,3,41,51123]，但是像[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]))

Answer 1

目前，您的排序不会根据值的最高位数对值进行重新排序。只有偶然地，41和{}是正确的（因为它们在初始列表中的相对顺序是正确的）。在

你应该总是建立一个新的名单，基于每个周期的排序。在

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 < base**(power+1):
                    result_list.append(x)
                else:
                    nums.append(x)
         power += 1
     return result_list

注意，基数排序不一定比基于比较的排序快。只有当要排序的项目数大于项目值的范围时，它才具有较低的复杂性。它的复杂性是O(len(nums) * log(max(nums)))，而不是{}。在