20

2 つの要素の比較に非常にコストがかかる場合を想像してみてください。

どのソートアルゴリズムを使用しますか?

平均的なケースで最も少ない比較を使用するソート アルゴリズムはどれですか?

比較される要素の多くが同一であると期待できるとしたら、たとえば比較の 80% でどうでしょうか。違いはありますか？

4

7 に答える 7

9

勝者は、比較を使用しないSleepSortです。

于 2012-10-26T18:50:47.540 に答える
2

おそらく挿入ソート

並べ替えは、彼らが言うように、悪魔が細部にある主題の1つです。通常、二次的な考慮事項がパフォーマンス入力パラメーターを支配します。

ただし、比較に非常に費用がかかり、ほとんどのキーが同一である場合、入力はすでにソートされているか、ほぼソートされていると見なされる可能性があります。

その場合、必要なのは、最速の最良のケースを持つ合理的なアルゴリズムであり、それはほぼ確実に挿入ソートになります。

于 2012-10-26T18:56:44.827 に答える
1

それはあなたが持っているデータに依存します。安定したアルゴリズムが必要かどうか?

データが一様にある場合は、バケットソート ( Θ(n), O(n^2)) を使用できます

カウントソート（あなたが探しているものだと思います）、それも安定したアルゴリズムですが、より多くのメモリが必要です（同一のレコードがたくさんある場合は少ないです）。

もちろんスリープソートも使えますが、データ量が多いとうまくいきません。

あなたの要素が80％同一である場合、同一（まったく同じ）であると言う簡単な方法がありますか？

于 2012-10-26T19:04:37.207 に答える
0

Shellsortは比較をあまり使用しません。

そして、あなたは同じ要素をたくさん持っています。カウントソートは仕事をするべきです

于 2012-10-26T18:46:40.303 に答える
0

おそらく、基数ソートのような非比較アルゴリズムが答えになるかもしれません。これは、一般的なケースでも高速であるためです（O（n）に時間がかかります）。要素間の比較も行いませんが、一方で多くのメモリを必要とします

于 2020-12-15T23:54:55.267 に答える
-1

分布の並べ替え（ハッシュ配列を使用）では、ほとんど比較が行われません。

m = max number  may appear in the input + 1
hash = array of size m
initialize hash by zeroes

for i = 0 to n - 1
    hash[input[i]] = hash[input[i]] + 1
j = 0
for i = 0 to m - 1
    while hash[i] > 0
        sorted[j] = i
        j = j + 1
        hash[i] = hash[i] - 1
于 2012-10-26T18:44:33.080 に答える