6

ソートされた値の代わりにソートされた順序のインデックスを返す高速で安定した基数ソートの実装 (フロートをサポート) を探しています。

彼の記事「Radix Sort Revisited」の Pierre Terdiman のバージョンは、私が望んでいることを正確に実行しますが、13 年以上前のものであり、最新のパイプライン CPU には適していません。

「Radix Tricks」の Michael Herf のRadixSort11は非常に高速ですが、唯一の問題は、インデックスではなく並べ替えられた値を返し、さらに入力配列の値を破損することです。

どんな助けでも大歓迎です。

4

3 に答える 3

2

次のいずれかを実行できます

  1. 各アイテムを展開して、元のインデックスを含めます (これは、最初のカウント パス中に行うことができます)。もちろん、並べ替えのためにインデックスの数字は無視されます。

  2. 値の代わりにインデックスをバケットに格納します。数字が必要になるたびに値を検索します。

前者はより多くのスペースを必要としますが、参照の局所性が向上し、後者はスペースを節約します。

于 2013-08-30T23:29:10.050 に答える