Python基數排序

我想在Python中實現基數排序。Python基數排序

我目前的程序工作不正常，因爲像[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]))

來源

2016-02-15 ytpillai

如果你關心速度，你不會創建自己的排序。 –

我試圖做最快的排序我可以 – ytpillai

基本上，我不希望它是O（n^2）或其他東西 – ytpillai

目前，您的排序不會根據任何內容重新排序值，而是根據其最高位進行排序。您只能偶然獲得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)))。

來源

2016-02-16 00:25:24 Blckknght

Python基數排序

回答

相關問題