这个bucket排序实现在做什么

Question

这是我在Python中进行bucket排序的代码。

from random import randrange

def insertion_sort(aList):
    for i in range(1, len(aList)):
        for j in range(i, 0, -1):
            if aList[j] < aList[j-1]:
                aList[j], aList[j-1] = aList[j-1], aList[j]
    return aList
def bucket_sort(aList):
    buckets =  [[]] * len(aList)
    for index, value in enumerate(aList):
        buckets_index = value * len(aList) // (max(aList) + 1)
        buckets[buckets_index].append(value)
answer = []
for bucket in buckets:
    answer.extend(insertion_sort(bucket))
    # answer += insertion_sort(bucket)
print(buckets[0])
print("n")
# return answer

aList = [randrange(10) for _ in range(100)]
print(aList)
print("n")
answer = bucket_sort(aList)
#print(answer)

发生了什么？当我运行代码时，我总是发现桶中的第一个列表已经排序，而桶中的其他列表都是它的副本。我需要每个列表的插入排序吗？我会用"answer"变量做什么？！

我主要依赖于这种可视化。

Answer 1

我马上注意到的一件事是，您将变量桶初始化为buckets = [[]] * len(aList)。这将生成一个空列表的相同副本的列表。因此，对该列表的任何修改都被复制到buckets的每个元素中。将此行更改为：

buckets =  [[] for _ in xrange(len(aList))]

要检查列表中的列表是否是单独的对象，可以检查它们的id：

print [id(x) for x in buckets]

这应该打印一个唯一数字的列表。

Answer 2

我认为这种bucket排序会更高效，更像Python。

def bucket(k):
    unique = list(set(k))
    values = [k.count(uni) for uni in unique]
    result = ([unique[uni] for i in range(values[uni])] for uni in range(len(unique)))
    result = sum(result, [])
    return result