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

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) 更改为 max-min，然后将 i=int(i) 更改为 i= i - min(并在最终结果中将 i 转换为 i + min

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