新しい（私が思うに）ソートアルゴリズムに注目してください。 似たようなものを探しましたが、類似物は見当たりませんでした。 このようなものを見たら教えてください。
ソートの本質は、ハッシュテーブル内のデータが既にソートされているように、ハッシュ関数と衝突解決が構築されることです。 ハッシュテーブルの配列を調べて、空でないソート済みデータを収集するだけです。
誰が気にする-私は猫をお願いします。
そのため、アルゴリズムは次のように機能します。
- 最初のパスでは、ハッシュテーブルインデックスの範囲（A min 、A max ）に値を投影するハッシュ関数の係数を計算するためのソースデータの最小値と最大値を見つけます。
- 2番目のパスでは、元の値をハッシュテーブルに挿入し、ハッシュ関数index =（ int ）（k *（A i -A min ）* TMPLEN /（A max -A min ））を使用してインデックスを計算します。
- 3番目のパスでは、ハッシュテーブルを調べて、並べ替えられたデータを元の配列にコピーします。
衝突を解決するには、ビジーセル（テーブルに挿入された値<=が記録されている場合）をスキップし、値が大きい場所に挿入する必要がある場合はテーブルの右部分（最初の空きセル）に移動します。
ハッシュテーブルの一時的な配列は、元の配列の2〜3倍です。 このため、衝突の解決を最適化し、右へのシフトのみを使用することができます。
このアルゴリズムは、比較と計算を組み合わせた安定した分類のクラスに属します。
計算の複雑さの範囲は、
O（n * log n） （Javaに組み込まれているクイックソートと比較すると理解できる）から最悪の場合の
O（n * n）までです。 デバイスを所有している場合は、正式に撤回できます。 私はすでにすべてを忘れています。 コメントであなたの考えを待っています。
均一な分布では、アルゴリズムはクイックソートよりも20〜25％高速に動作することがわかりました。
メモリのオーバーヘッドは
O（n）です。
クイックソートと比較すると、ソースデータ値の数が少ないと、多くの衝突を解決する必要があるため、アルゴリズムが非常に劣化していることがわかりました。
ただし、マージ（500個の値のブロックで並べ替え）と組み合わせると、純粋なマージよりも高速な並べ替えに匹敵するパフォーマンスを達成できました。
利点：
- 並列ウェル（非再帰的ブロックマージを使用する場合）;
- 迅速な並べ替えに見合ったパフォーマンス。
- 分布がわかっている場合は、ハッシュ関数を調整して、ハッシュテーブルの入力を最適化できます。
短所：
- メモリが多すぎる。
- 値の範囲が狭い場合、または分布が非常に不均一な場合、パフォーマンスが低下します。
このアルゴリズムが実際に役立つかどうかはわかりませんが、アカデミックな学習には絶対に害はありません。
Javaでテストするための私のソースコード。
さまざまなモードでテストできるパラメーターで遊ぶ。 たとえば、SORTBLOCK = SOURCELENを設定すると、純粋なハッシュアルゴリズムが適用されます。 MIN_VALおよびMAX_VALを使用して、乱数を生成するための値の範囲を指定できます。
SOURCELEN <300の場合、ソートされたデータはコンソールに出力されます。 配列の空の値については、ゼロを選択したため、範囲に含めないでください。
そして、パフォーマンスの測定が完全に正しいわけではないことを理解しています。 しかし、予備評価のためにそれは行います。 時間があれば、同僚がアドバイスするように、特別なフレームワークを試します。
import java.util.Arrays; import java.util.Date; import java.util.Random; public class HashSort {