2

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

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

4

3 回答 3

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 出现的次数。我们只需遍历列表并增加适当的数组位置。然后我们按顺序遍历数组并获得排序列表。

于 2012-10-01T22:34:00.460 回答
0

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

于 2012-10-01T22:26:35.697 回答
0

您描述的算法似乎是“计数排序”的变体（我被教导为“图书馆员排序”，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

于 2012-10-01T22:27:49.613 回答