ほとんどの値の配列がありますが、完全にはソートされておらず、いくつかの値が置き換えられています (たとえば、100000 で 50)。最も効率的に並べ替える方法は？(ここではパフォーマンスが絶対に重要であり、O(N) よりもはるかに高速である必要があります)。
Smoothsort については知っていますが、Java の実装が見つかりません。すでに実装されているかどうか知っている人はいますか？または、スムーズソートの代わりにこのタスクに何を使用できますか?
12251 次
10 に答える
19
実際、ウィキペディアにはスムーズソートの Java 実装が含まれています。ここで見つけることができます：
于 2009-09-07T20:23:46.900 に答える
10
シェーカーソート
実装が簡単な単純なアルゴリズムが必要な場合は、シェーカーソートを実行できます。ほぼソートされた入力で適切に機能します。
于 2009-09-07T20:32:53.597 に答える
7
Botz3000 が指摘したように、このような操作は O(N) よりも高速に実行できません。任意のアルゴリズムの最も基本的な要素は、配列内の順不同のエントリを見つけることです。これには、何をすべきかを理解する前であっても、O(N) が必要です。
実際に「順不同」の要素の数が要素の総数よりも桁違いに小さい場合は、次のアルゴリズムを使用できます (リンクされたリストを想定)。
- すべての順不同のアイテムを見つけて、元のリストから別のリスト O(N) に抽出します。
- 結果は、ソートされたリストと短い抽出リストの 2 つのリストになります。
- 抽出された要素ごとに、並べ替えられたリストに挿入します。それはそれぞれについて O(log(N)) になり、合計は O(Xlog(N)) になります。ここで、X は抽出された要素の数です。X が N に対して非常に小さい場合、合計は O(N) になります。
于 2009-09-07T20:23:15.723 に答える
6
これには多くの優れたアルゴリズムがあります。
Smoothsort は私の個人的なお気に入りです...なぜそれがうまく機能するのか知りたい場合は、実際にここですべての計算を行いました。
既にソートされたデータに対するかなり優れたアルゴリズムは、ナチュラル マージソートです。これは、マージソートのボトムアップ バージョンであり、入力をソートされた部分範囲のシーケンスとして扱い、隣接するソートされた範囲をマージする範囲で複数のパスを作成することによって機能します。データが既にソートされている場合は O(n) 時間で実行され (ソートされた範囲が 1 つしかないことを検出できるため)、最悪の場合は O(n lg n) で実行されます。このアルゴリズムは、データが「ブロックソート」されている場合に非常にうまく機能します。つまり、並べて配置された多数のソートされたブロックで構成されています。
直接挿入ソートは、大部分がソートされたデータに対しては確実にうまく機能しますが、多くの入力では非常にひどく劣化する可能性があります。一部の非常に優れたソート ( introsortなど) は、実際には挿入ソートのこのプロパティを使用して、入力に対して「クリーンアップ ステップ」を実行します。
于 2010-11-09T07:09:20.210 に答える
4
[Sun] JDK7 には、Tim ソート(Python から) の実装があります (または実装される予定です)。これは、配列に既に存在する順序を利用するマージ ソートです。
于 2009-09-07T20:58:51.807 に答える
3
Smoothsort または Timsort は優れたアルゴリズムであり、使用するのが賢明です。
あなたが気づいていないかもしれないことは、謙虚な挿入ソートが適応的であるということです。確かに、あなたが持っているように、本当にほとんどソートされたリストの場合、私の理解（参照でバックアップすることはできません）は、より洗練されたアルゴリズムよりも高速であるということです。問題は、入力がほとんどソートされていない場合、急速に O(n^2) に劣化することです。それでも、正しく実装するのは非常に簡単なので、入力が常にほぼソートされていることが確実にわかっている場合は、それを選択することをお勧めします。
于 2009-11-21T18:10:16.343 に答える
2
それをテーブルに置くために、うまく実装されたバブルソートは確かにここで最も単純なアルゴリズムです。O（n * m）の最悪の場合、mは変位の数です。m部分は変位のパターンに大きく依存し、通常、全体の複雑さはO（n）になります。
于 2009-09-07T20:35:42.020 に答える
0
O（N）に到達することは不可能ですが、マルチコアマシン（私が持っている）を想定すると、並列ソートアルゴリズムを使用して少しチートすることができます。
于 2009-09-07T20:35:53.923 に答える
0
学校でShell の sortと呼ばれるものを実装します。それは、サブ配列のバブルソートです。ステップ k のサブ配列は、インデックス 0、k、2k、3k... を持つ要素の配列です。
k = 3i+1 を選択し、複数のバブル ソートを実行すると、高いものから 0 まで、ほぼソートされた配列で時間は短くなります。
于 2009-09-07T20:55:10.550 に答える