2

一意である必要のない n 個の正の整数キーのリスト L をソートするアルゴリズム。O(n+N)どこの複雑さを持っている必要がありN = maxL(i) - minL(i)ますか?

私はマージソートのようなものを試しましたが、それは私に与えますO(nlogn). 余分なスペースが与えられO(N)ているので、O(n)複雑にする必要はありません。ただし、私のマージソートのようなアルゴリズムが 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 に変換するというものです。(現在、最小 = 0 および最大 = old_max - 最小)。ここで、配列の i 番目の位置は、number 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 に答える