为什么"计数排序"不是一种更广泛使用的算法？

Question

我正在绘制一些大型学术文件中的字母频率.作为此过程的一部分,是将这些文档的大量剪辑中的字母排序为字母顺序.我使用Python's内置的排序功能,我开始怀疑是否可以让它更快.然后我写了以下函数:

  def count_sort(l):
        items = {'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,'l':0,'m':
 0,'n':0,'o':0,'p':0,'q':0,'r':0,'s':0,'t':0,'u':0,'v':0,'w':0,'x':0,'y':0,'z'
:0}
        for item in l:
            items[item] += 1
        sort_l = []
        for key in items:
            sort_l += key*items[key]
        return sort_l

当测试此代码与sorted上一个10000文本的字母的长字符串,它几乎20X快.

有了这样的性能提升,为什么这个排序算法不在标准中libs？

Answer 1

您重新发现了计数排序算法.

引用维基百科:

对于最大键值明显小于项目数的问题实例,计数排序可以高度节省空间,因为它使用除输入和输出数组之外的唯一存储是使用空间O(k)的Count数组).

计数排序算法变得越来越有效(相对),正在排序的项目总数与被排序的唯一项目的数量之间的差异越大.

您可以看到为什么必须查看您自己的代码或Wikipedia示例代码:

# calculate the histogram of key frequencies:
for x in input:
    count[key(x)] += 1

# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount

# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1

return output

你的函数中有2个for循环:第一个迭代你正在排序的字母,第二个循环遍历items字典.正如我之前提到的那样,这意味着项目字典比您正在排序的列表要小得多,但如果相对于被排序的项目数量的唯一元素的数量增加,它很快变得非常低效.

就像@BrenBarn回答的那样,只有当你确切地知道了什么字符时,你才愿意忽略任何其他字符.虽然在你给出的例子中计算排序是高效的,但排序字母的问题并不是最常见的排序问题.

下面我修复了你的函数,通过遍历列表而不是遍历字典中的键来打印字母(因为Python的字典没有被排序)

def count_sort(l):
    letters = [chr(i) for i in range(97, 122)]
    items = dict()
    for letter in letters:
        items[letter] = 0
    for item in l:
        items[item] += 1
    sort_l = list()
    for letter in letters:
        sort_l.extend(letter*items[letter])
    return sort_l