计数排序的实现

Question

我做了以下计数排序的实现。我不认为我完全理解这个算法，但是这个实现似乎是正确的。

我使用了集合模块中的Counter字典。这似乎是处理计数部分的最佳方法。但我还没见过有人用它来实现计数排序。

有什么方法来改进代码吗？

from random import randrange
from collections import Counter
from copy import deepcopy

def counting_sort(aList, length):
    """
    counting sort does not work for negative numbers
    counting sort assumes that each element is SMALL INTEGER

    running time is O(maxVal - minVal) ---> Linear

    (Useful only when the difference between maxVal and minVal is not large)
    """
    list_copy = deepcopy(aList)  # a copy so that I can return it and check it against the original list applied to sorted function
    c = Counter()

    for num in list_copy:
        c[num] += 1

    index = 0

    # for i in range(len(c)):
        # while 0 < c[i]:
            # list_copy[index] = i
            # c[i] -= 1
            # index += 1
    for key in c:
        while c[key] > 0:
            list_copy[index] = key
            c[key] -= 1
            index += 1

    return list_copy


aList = [randrange(100) for _ in range(1000)]
after = counting_sort(aList, len(aList))
print(after == sorted(aList))

Answer 1

您的代码不可靠，因为Counter是无序的。在许多情况下，它得到了正确的结果，但不依赖于它。我不会给出另一种解决方案，因为code是为了改进现有代码，而不是为了编写新代码。虽然您的代码不应该用于排序，但我对您所做的工作有一些评论。

您没有使用length，那么为什么需要它作为一个参数呢？

不要创建列表的副本，然后更改每个索引，而是创建一个空列表并向其添加内容。

您的Counter实现没有利用它。你使用它的方式和你使用字典的方式非常相似。只需使用Counter(aList)

您可以使用for key in c:简化您的itertools.repeat循环。注意:不要将它用于可变对象。

你的名字不一致。PEP 8建议使用snake_case，但同时使用snake_case和pascalCase。你不需要遵守PEP 8的S建议，但你至少应该保持一致。例如，您还应该使用比c更多的描述性名称。

新的守则：

from collections import Counter
from itertools import repeat

def counting_sort(number_list):
    """
    counting sort does not work for negative numbers
    counting sort assumes that each element is SMALL INTEGER

    running time is O(maxVal - minVal) ---> Linear

    (Useful only when the difference between maxVal and minVal is not large)
    """

    sorted_list = []
    for value, amount in Counter(number_list).items():
        sorted_list.extend(repeat(value, amount))

    return sorted_list