如何使用队列进行基数排序？

我正在使用Python 3x。

这是我尝试使用队列作为分档，因为队列是先进先出的数据结构。

from my_queue import Queue 
def rsort(n): 
    '''(list of int) -> list of int 
    ''' 
    list_length = len(n) 
    val = 0 
    mod = 10 
    k = 1 
    bin_list = [] 
    alist = n 
    for bins in range(0,10): 
     bin_list.append(Queue()) 

    while val == 0: 
     for num in alist: 
      sig_dig = num % mod 
      sig_dig = int(sig_dig/k) 
      bin_list[sig_dig].enqueue(num) 

     if bin_list[0].size() == list_length: 
      alist.append(bin_list[0].dequeue()) 

     else: 
      mod = mod * 10 
      k = k * 10    

     new_list = [] 
     for bins in bin_list: 
      if not bins.is_empty(): 
       new_list.append(bins.dequeue()) 
      alist = new_list 

     return alist

我的代码工作完全正常的小的数字，如：[3,2,6,5,8,7]

但是当列表中的值变大，如：[240, 28, 5, 18, 140, 2]

我的程序不再对列表进行排序，数字最终错过和无序。

我一直在玩弄我的程序很多，但我不能修复它:(

来源

2013-03-21 UberNate

你是什么'Queue'类的API？具体而言，“出列”是否只从其中删除一个项目，或同时删除所有值？ – Blckknght 2013-03-21 12:37:44

有一对夫妇的事情，似乎错在你的代码。我不知道到底是哪的这些都是导致你看到的问题，但可能所有这些都需要修复才能得到正确的结果。

首先，快速注意：您可以通过仅使用一个整数来简化逻辑在每个数字中找到正确的数字我建议一个从零开始并达到某个值的数值（您想要排序的数字的数量）您可以使用sig_dig = num // 10**k % 10找到给定列表项的数字值//运算符强制Python使用“floor division”，截断正常分割的非整数部分。

无论如何，第一个问题是你在val == 0上循环，但是你永远不会修改val，并且你在循环结束之前返回一个值（所以你永远不会这么做）。您可以通过计算列表中最长值的位数来解决此问题，例如max_digits = int(math.ceil(math.log(max(lst), 10)))。然后你可以让你的循环变得更简单：for k in range(max_digits):

我看到的下一个问题是你可能没有正确地从箱子中取回数值。您只需拨打dequeue一次，但您应该反复调用，直到队列为空。或者，如果我误解了您正在使用的Queue API，并且dequeue会返回所有队列的值，则需要使用extend将它们全部添加到列表中。

这里就是我想你想拥有，到底：

import math 

from my_queue import Queue 

def rsort(n): 
    '''(list of int) -> list of int 
    ''' 
    bin_list = [Queue for _ in range(10)] 
    max_digits = int(math.ceil(math.log(max(lst), 10))) # calculate # of digits 

    for k in range(max_digits): 
     for num in alist: 
      sig_dig = num/10**k % 10 # find digit's value 
      bin_list[sig_dig].enqueue(num) 

     n = [] # we can reuse the name `n`, rather than using a different name 
     for bins in bin_list: 
      while not bins.is_empty(): # loop to dequeue all values 
       n.append(bins.dequeue()) 

    return n # the return statement is outside the loop!

来源

2013-03-21 13:04:20 Blckknght

如何使用队列进行基数排序？

回答

相关问题