Python Radix排序

发布时间：2020-12-20 13:10:01 所属栏目：Python 来源：网络整理

导读：我正在尝试在 python中实现Radix排序. 我当前的程序工作不正常,因为像[41,51,2,3,123]这样的列表将正确排序到[2,41,123],但类似于[52,42,23]将成为[23,52,51](52和51在错误的地方). 我想我知道为什么会这样,因为当我比较十位的数字时,我也不比较单位(对于10

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

我当前的程序工作不正常,因为像[41,51,2,3,123]这样的列表将正确排序到[2,41,123],但类似于[52,42,23]将成为[23,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,6,12,21,415,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 < base**(power+1):
                    result_list.append(x)
                else:
                    nums.append(x)
         power += 1
     return result_list

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!