2

O(n log n) よりも高速な .Net Doubles 用の安定した並べ替えアルゴリズムが必要です。

基数ソートを考えています。しかし、私が正しく理解している場合、パフォーマンスは O(nk) であり、Double をソートしているため、k = 8 です。n > 2980 の場合、これは O(n log n) ソート (つまり QuickSort) よりも高速になります。 (これは正しいですか??) 私の場合、n はより一般的には 500 または 1000 前後になりますが、それよりもはるかに大きい場合もあります。(そして、はい、この並べ替えは非常に頻繁に行われ、プロファイリング分析に基づいてその速度が重要になります)。

では、QuickSort を使い続ける必要がありますか、それとも他のより高速な代替手段はありますか? バケットソートはどうですか？C# または VB.NET での適切な実装を探しています。

編集:現在、安定した QuickSort 実装を使用しています。

編集: 浮動小数点値については、この Radix の実装を参照してください: http://codercorner.com/RadixSortRevisited.htm。これによると、k は Doubles の場合は 9 になります。

4

2 に答える 2

2

実際、doulbes の基数ソートには複雑さ n*k があり、k は 8 ではなく 64 です (従来の基数ソートは数値のバイナリ表現を使用します)。これは、どの入力に対しても高速になることはほとんどありません。すでに述べたように、少数の入力値についてはクイック ソートの方が確実に速くなります。また、C++ での std::sort の実装の一部では、O(n^2) アルゴリズムを使用して少数の値のソートを完了することに注意してください (実際には小さい数) であり、通常は挿入ソート (こちらをご覧ください) になります。したがって、いくつかのアルゴリズム間のハイブリッドが最適な場合があります。

于 2012-04-25T19:13:52.623 に答える
1

基数ソートは O(n*k) です。ここで、k は log(n) になる傾向があります。k は桁数であり、桁数は最大数の大きさの対数によって変化するためです。

また、float や double のバイナリ表現を調べても、ソートできるものは得られません。科学表記法を避ける場合は、小数点以下の桁数が一定の 10 進文字列に変換し、基数で並べ替えることができます。

おそらく、.Net ソート メソッド (おそらくかなり最適化されている) または timsort のいずれかを使用するのが最適です。

漸近分析では、軸に近いグラフ上の絶対位置ではなく、曲線の形状を見ています。これは、n が十分に大きい場合、軸を交差する場所よりも形状が重要になるためです。

したがって、巨大なリストをソートしていない場合は、クイックソートや挿入ソートなどのより少ないソートを使用することをお勧めします。

タイト ループでの並べ替えが良い考えになることはめったにありません。通常、そのような設計は、ヒープ、トレプ、赤黒ツリー、スキップ リスト、スプレイ ツリー、またはその他の log(n) データ構造を使用するものに置き換える方が適切です。

クイックソートは安定しているとは思いませんが、少しパフォーマンスが低下する可能性があります。

mergesort は非常にコーディングが簡単で、timsort に関連しており、安定しています。timsort も安定しています。

詳細をサポートするグラフを次に示します。

いくつかの種類の線形 - 線形グラフ

于 2012-04-25T21:29:02.887 に答える