对 n 个正整数键的列表 L 进行排序的算法，这些键不需要是不同的.应该具有 O(n+N) 的复杂度，其中 N = ma

Question

算法，用于对不需要不同的n个正整数键的列表L进行排序。应该有O(n+N)的复杂性N = maxL(i) - minL(i)在哪里？

我

尝试了合并排序之类的东西，但这给了我O(nlogn).我得到了额外的空间O(N)所以它不必O(n)复杂性。但是，我不知道我的类似合并排序的算法是否允许采用多个log n次。请帮忙？

Answer 1

这是我的存储桶排序（基数排序）实现。

def _sort(_list):
    buckets=[0]*len(_list)
    for i in _list:
        i=int(i)
        assert(0<=i<len(_list))
        buckets[i]+=1
    result=[]
    for num,count in enumerate(buckets):
        result.extend([num]*count)
    return result

您需要将 len（_list） 更改为最大最小值，然后将 i=int（i） 更改为 i= i - min（并在最终结果中将 i 转换为 i + min

这个想法是我们将每个数字 i 转换为 i -min.（现在 min=0 和 max = old_max - min）。现在在我们的数组中，第 i 个位置表示数字 i-min 出现的次数。我们只需浏览列表并增加适当的数组位置。然后我们按顺序浏览数组并得到排序列表。

Answer 2

你描述的算法似乎是"计数排序"的变体（我被教导为"图书馆员排序"，ordinamento del libraio）

这是来自维基百科的伪代码：

''' allocate an array Count[0..k] ; initialize each array cell to zero ; THEN '''
for each input item x:
    Count[key(x)] = Count[key(x)] + 1
total = 0
for i = 0, 1, ... k:
    c = Count[i]
    Count[i] = total
    total = total + c
''' allocate an output array Output[0..n-1] ; THEN '''
for each input item x:
    store x in Output[Count[key(x)]]
    Count[key(x)] = Count[key(x)] + 1
return Output

http://en.wikipedia.org/wiki/Counting_sort

Answer 3

最好的排序算法（合并排序、快速排序等）O(nlogn)复杂，但也有一些特殊情况。（提示：您的问题的特殊情况是它们都是整数）