1

FFT変換後に数値をソートする最速のアルゴリズムを探しています-絶対値の実数のみ。values)=2^19 要素の 1 次元配列の倍精度の有理数。メグレソートがいいと思いますが…

4

5 に答える 5

2

質問が a の並べ替えに関するものである場合はdouble[]、 を使用しますArrays.sort。これはクイックソートの派生物です。

あなたが持っているものが倍精度の分数を表すオブジェクトの配列である場合、そのクラスは を実装する必要がComparableありますがArrays.sort(Object[])、ここでも timsort (Java 7 以降) を使用する が最適です。ただし、パフォーマンスはあなたの手に委ねられていることに注意してください。 の実装を台無しにしないでくださいcompareTo。

于 2012-10-27T10:34:44.533 に答える
0

Java7の情報についてArrays.sortは、 Timsort を使用します。

Timsort は、マージ ソートと挿入ソートから派生したハイブリッド ソート アルゴリズムであり、多くの種類の実世界のデータに対して適切に機能するように設計されています。Python プログラミング言語で使用するために、2002 年に Tim Peters によって発明されました。このアルゴリズムは、既に順序付けされているデータのサブセットを見つけ、そのサブセットを使用してデータをより効率的に並べ替えます。これは、ランと呼ばれる識別されたサブセットを、特定の基準が満たされるまで既存のランとマージすることによって行われます。Timsort は、バージョン 2.3 以降の Python の標準ソート アルゴリズムです。Java SE 7 および Android プラットフォームで配列をソートするためにも使用されるようになりました。

于 2012-10-27T10:41:59.503 に答える
0

どのアルゴリズムを使用するかは、ソートするオブジェクトの種類ではなく、オブジェクトがどの程度混乱しているかによって異なります。

さまざまな状況でさまざまな標準アルゴリズムがどのように機能するかの比較については、http://www.sorting-algorithms.com/を参照してください。

于 2012-12-17T09:57:07.703 に答える
0

20 万分の 1 の要素を並べ替えるだけの場合は、多くのオプションがあります。おそらく、使用している言語に含まれる標準のソート アルゴリズムで問題を解決できます。

要素間にはかなりのばらつきがあるようですが、FFT 変換によって既にソートされた数値が大量に実行される配列が生成されるかどうかはわかりません。その場合、Quicksort は避けた方がよいでしょう。ティムソートはこういうのが得意だと聞きました。

于 2013-11-11T03:01:42.450 に答える