ソートの本質は、ハッシュテーブル内のデータが既にソートされているように、ハッシュ関数と衝突解決が構築されることです。 ハッシュテーブルの配列を調べて、空でないソート済みデータを収集するだけです。
誰が気にする-私は猫をお願いします。
そのため、アルゴリズムは次のように機能します。
- 最初のパスでは、ハッシュテーブルインデックスの範囲（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 { // static int SOURCELEN = 1000000; int source[] = new int[SOURCELEN]; // int quick[] = new int[SOURCELEN]; // static int SORTBLOCK = 500; static int k = 3; // static int TMPLEN = (SOURCELEN < SORTBLOCK * k) ? SORTBLOCK * k : SOURCELEN; int tmp[] = new int[TMPLEN]; // static int MIN_VAL = 10; static int MAX_VAL = 1000000; int minValue = 0; int maxValue = 0; double hashKoef = 0; long finishTime = 0; long startTime = 0; long finishTimeQuick = 0; long startTimeQuick = 0; // public void randomize() { int i; Random rnd = new Random(); for(i=0; i<SOURCELEN; i++) { int rndValue = MIN_VAL + ((int)(rnd.nextDouble()*((double)MAX_VAL-MIN_VAL))); source[i] = rndValue; } } // - public void findMinMax(int startIndex, int endIndex) { int i; minValue = source[startIndex]; maxValue = source[startIndex]; for(i=startIndex+1; i<=endIndex; i++) { if( source[i] > maxValue) { maxValue = source[i]; } if( source[i] < minValue) { minValue = source[i]; } } hashKoef = ((double)(k-1)*0.9)*((double)(endIndex-startIndex)/((double)maxValue-(double)minValue)); } // public void stickParts(int startIndex, int mediana, int endIndex) { int i=startIndex; int j=mediana+1; int k=0; while(i<=mediana && j<=endIndex) { if(source[i]<source[j]) { tmp[k] = source[i]; i++; } else { tmp[k] = source[j]; j++; } k++; } if( i>mediana ) { while(j<=endIndex) { tmp[k] = source[j]; j++; k++; } } if(j>endIndex) { while(i<=mediana) { tmp[k] = source[i]; i++; k++; } } System.arraycopy(tmp, 0, source, startIndex, endIndex-startIndex+1); } // boolean shiftRight(int index) { int endpos = index; while( tmp[endpos] != 0) { endpos++; if(endpos == TMPLEN) return false; } while(endpos != index ) { tmp[endpos] = tmp[endpos-1]; endpos--; } tmp[endpos] = 0; return true; } // - public int hash(int value) { return (int)(((double)value - (double)minValue)*hashKoef); } // public void insertValue(int index, int value) { int _index = index; while(tmp[_index] != 0 && tmp[_index] <= value) { _index++; } if( tmp[_index] != 0) { shiftRight(_index); } tmp[_index] = value; } // public void extract(int startIndex, int endIndex) { int j=startIndex; for(int i=0; i<(SORTBLOCK*k); i++) { if(tmp[i] != 0) { source[j] = tmp[i]; j++; } } } public void clearTMP() { if( tmp.length < SORTBLOCK*k) { Arrays.fill(tmp, 0); } else { Arrays.fill(tmp, 0, SORTBLOCK*k, 0); } } // public void hashingSort(int startIndex, int endIndex) { // 1. findMinMax(startIndex, endIndex); // 2. clearTMP(); // 3. - for(int i=startIndex; i<=endIndex; i++) { insertValue(hash(source[i]), source[i]); } // 4. extract(startIndex, endIndex); } // public void sortPart(int startIndex, int endIndex) { if( (endIndex - startIndex) <= SORTBLOCK ) { hashingSort(startIndex, endIndex); return; } int mediana = startIndex + (endIndex - startIndex) / 2; sortPart(startIndex, mediana); sortPart(mediana+1, endIndex); stickParts(startIndex, mediana, endIndex); } public void sort() { sortPart(0, SOURCELEN-1); } // public String toString() { int i; String res = ""; res += "Source:"; if( SOURCELEN < 300) { for(i=0; i<SOURCELEN; i++) { res += " " + source[i]; } } res += "\n"; res += "Quick: "; if( SOURCELEN < 300) { for(i=0; i<SOURCELEN; i++) { res += " " + quick[i]; } } res += "\n"; res += "len: " + SOURCELEN + "\n"; res += "hashing&merge sort time: " + (finishTime - startTime) + "\n"; res += "quick sort time: " + (finishTimeQuick - startTimeQuick) + "\n"; return res; } // public void copyToQuick() { System.arraycopy(source, 0, quick, 0, source.length); } public static void main(String[] args) { HashSort hs = new HashSort(); hs.randomize(); hs.copyToQuick(); hs.startTime = (new Date()).getTime(); hs.sort(); hs.finishTime = (new Date()).getTime(); hs.startTimeQuick = (new Date()).getTime(); Arrays.sort(hs.quick); hs.finishTimeQuick = (new Date()).getTime(); System.out.println(hs.toString()); } }