ソート アルゴリズムは多くの場所で使用されていますが、私は最近そのアルゴリズムを再検討し、簡単に実装しました。ここに記録し、将来のレビューのためにいくつかの資料を保存します。
さっそく、古典的な並べ替えアルゴリズムを 1 つずつ見てみましょう。
1. 並べ替えを選択します
選択ソートの基本的な考え方は、配列を走査するプロセス中に、i がソートする必要がある現在のシーケンス番号を表す場合、残りの [i...n-1] の中から最小値を見つける必要があるということです。 、見つかった最小値を i にポイントし、値が交換されます。要素を決定する各プロセスには、最大値を選択するサブプロセスがあるため、人々はそれを明確に選択ソートと呼んでいます。例を挙げてみましょう:
初期値：[38、17、16、16、7、31、39、32、2、11]
i = 0: [2, 17, 16, 16, 7, 31, 39, 32, 38, 11] (0 番目 [38]<->8 番目 [2])
i = 1: [2、7、16、16、17、31、39、32、38、11] (1 番目 [38]<->4 番目 [17])
i = 2: [2、7、11、16、17、31、39、32、38、16] (2 番目 [11]<->9 番目 [16])
i = 3: [2、7、11、16、17、31、39、32、38、16] (交換は必要ありません)
i = 4: [2、7、11、16、16、31、39、32、38、17] (4 番目 [17]<->9 番目 [16])
i = 5: [2、7、11、16、16、17、39、32、38、31] (5 番目 [31]<->9 番目 [17])
i = 6: [2、7、11、16、16、17、31、32、38、39] (6 番目 [39]<->9 番目 [31])
i = 7: [2、7、11、16、16、17、31、32、38、39] (交換は必要ありません)
i = 8: [2、7、11、16、16、17、31、32、38、39] (交換は必要ありません)
i = 9: [2、7、11、16、16、17、31、32、38、39] (交換は必要ありません)
この例からわかるように、選択ソートが進むにつれて (i が徐々に増加していきます)、比較の数はどんどん減っていきます。ただし、配列が最初に順序付けされているかどうかに関係なく、選択ソートは選択比較を実行します。したがって、指定された長さの配列の場合、選択ソートの比較の数は固定されます: 1 + 2 + 3 + … + n = n * (n + 1) / 2。 、交換の回数は初期配列の順序に関係します。初期配列の順序がランダムな場合、最悪の場合、配列要素は n 回交換され、最良の場合は 0 回になる可能性があります。配列自体はシーケンスです)。
選択ソートの時間計算量と空間計算量はそれぞれ O(n2) と O(1) であると推測できます (選択ソートには配列要素の交換のための追加スペースのみが必要です)。
実装コード:
次のようにコードをコピーします。
/**
*選択の並べ替え
*/
SELECTION(新しいソータブル() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = 配列の長さ;
for (int i = 0; i < len; i++) {
int 選択 = i;
for (int j = i + 1; j < len; j++) {
int Compare = array[j].compareTo(array[selected]);
if (比較 != 0 && 比較 < 0 == 昇順) {
選択された = j;
}
}
交換(配列、i、選択された);
}
}
})
2. 挿入ソート
挿入ソートの基本的な考え方は、配列を走査するプロセス中に、シリアル番号 i より前の要素、つまり [0..i-1] がソートされていると仮定して、この行程で正しい位置を見つける必要があるということです。 i に対応する要素 x の k、この位置 k を見つける過程で、比較された要素は 1 つずつ後方に移動され、要素 x のための「スペース」が確保されます。最後に、k に対応する要素の値が割り当てられます。 x. 挿入ソートもソートの特性に応じて名前が付けられます。
以下に例を示します。赤でマークされた番号は、この並べ替えに参加しない要素です。 2 番目の並べ替えに参加している要素は [11, 31, 12] で、挿入する必要がある要素は 12 ですが、12 は現在正しい位置にないため、次のように挿入する必要があります。前の要素 31 と 11 を順番に並べます。比較し、比較中に比較要素を移動し、12 より小さい最初の要素 11 を見つけたら比較を停止します。このとき、31 に対応するインデックス 1 が 12 を挿入する必要がある位置です。
イニシャル: [11、31、12、5、34、30、26、38、36、18]
最初のパス: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] (移動された要素なし)
2 番目のトリップ: [11、12、31、5、34、30、26、38、36、18] (31 は後退します)
3 番目のトリップ: [5、11、12、31、34、30、26、38、36、18] (11、12、31 はすべて後退)
4 番目のパス: [5、11、12、31、34、30、26、38、36、18] (移動要素なし)
5 番目のトリップ: [5、11、12、30、31、34、26、38、36、18] (31、34 は後退)
6 番目のトリップ: [5、11、12、26、30、31、34、38、36、18] (30、31、34 は後退します)
7 番目のパス: [5、11、12、26、30、31、34、38、36、18] (移動要素なし)
8 番目のトリップ: [5、11、12、26、30、31、34、36、38、18] (38 が後退)
9 番目のトリップ: [5、11、12、18、26、30、31、34、36、38] (26、30、31、34、36、38 は後方に移動)
挿入ソートは、ソート処理中に配列要素の最初の部分がソートされているという事実を利用できるため、選択ソートよりも優れています。もちろん、この利点は、最初の順序に依存します。最終的に、悪いケース (指定された配列がたまたま逆順になった場合) では、挿入ソートに必要な比較と移動の数は 1 + 2 + 3... + n = n * (n) になります。 + 1) / 2. この極端なケースでは、挿入ソートのソート効率は選択ソートよりもさらに悪くなります。したがって、挿入ソートは不安定なソート方法であり、挿入効率は配列の初期順序と密接に関係しています。一般に、挿入ソートの時間計算量と空間計算量はそれぞれ O(n2) と O(1) です。
実装コード:
次のようにコードをコピーします。
/**
※インサートソート
*/
INSERTION(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = 配列の長さ;
for (int i = 1; i < len; i++) {
T toInsert = 配列[i];
int j = i;
for (; j > 0; j) {
int 比較 = 配列[j - 1].compareTo(toInsert);
if (比較 == 0 || 比較 < 0 == 昇順) {
壊す;
}
配列[j] = 配列[j - 1];
}
配列[j] = 挿入;
}
}
})
3. バブルソート
バブルソートは最も古典的なソートアルゴリズムと言え、私が学生時代に初めて触れたのはこのアルゴリズムであり、実装方法が最もシンプルなため、2 レベルの for ループです。内側のループでは、隣接する 2 つの要素が逆順であるかどうかを判断し、その場合は 2 つの要素を交換し、外側のループを 1 回実行して、配列内の残りの要素のうち最小の要素を前に「フローティング」します。バブル仕分け。
いつものように簡単な例を挙げてみましょう。
初期状態: [24、19、26、39、36、7、31、29、38、23]
内層の最初のトリップ: [24、19、26、39、36、7、31、29、23、38] (9 番目 [23]<->8 番目 [38)]
内層の 2 パス目: [24、19、26、39、36、7、31、23、29、38] (8 番目 [23]<->7 番目 [29])
内層の 3 パス目: [24、19、26、39、36、7、23、31、29、38] (7 番目 [23]<->6 番目 [31])
内側レイヤーの 4 番目のパス: [24、19、26、39、36、7、23、31、29、38] (7 と 23 はすべて正しい順序であり、交換する必要はありません)
内層の 5 番目のトリップ: [24、19、26、39、7、36、23、31、29、38] (5 番目 [7]<->4 番目 [36])
内層の 6 回目: [24, 19, 26, 7, 39, 36, 23, 31, 29, 38] (4 回目 [7]<->3 回目 [39])
内層の 7 パス目: [24, 19, 7, 26, 39, 36, 23, 31, 29, 38] (3rd [7]<->2nd [26])
内層の8パス目：[24, 7, 19, 26, 39, 36, 23, 31, 29, 38] (2nd [7]<->1st [19])
内層の 9 回目のトリップ: [7、24、19、26、39、36、23、31、29、38] (1 番目 [7]<->0 番目 [24])
……。
実際、バブル ソートは選択ソートと似ており、比較の数は同じです (n * (n + 1) / 2)。ただし、バブル ソートは最小値を選択するプロセスで追加の交換を実行します (バブル ソートで必要なのは、最小値のみです)。隣接する要素の順序が正しくないことが判明した場合は、それに応じて交換されます。選択ソートは、内部ループの比較が完了した後の状況に応じて交換するかどうかを決定するだけなので、私の意見では、選択ソートが属します。バブルソートの改良版。
実装コード:
次のようにコードをコピーします。
/**
* バブルソートは挿入ソートとよく似ています。
*/
BUBBLE(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int の長さ = 配列の長さ;
int lastExchangedIdx = 0;
for (int i = 0; i < length; i++) {
// 交換が false であったかどうかを識別するフラグをマークします
ブール値 isExchanged = false;
// 最後の比較と交換はインデックス i に到達する前に行われました
int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;
for (int j = 長さ 1; j > currOrderedIdx; j) {
int 比較 = 配列[j - 1].compareTo(配列[j]);
if (比較 != 0 && 比較 > 0 == 昇順) {
交換(配列、j 1、j);
isExchanged = true;
lastExchangedIdx = j;
}
}
// 交換が発生しない場合は、配列がすでに整っていることを意味します
if (isExchanged == false) {
壊す;
}
}
}
})
4. 丘の選別
ヒル ソートは、挿入ソートで大きな配列を扱うときに移動する要素が多すぎるという問題に遭遇したために生まれました。ヒル ソートの考え方は、大きな配列を、配列 [1、2、3、4、5、6、7、8] のようなギャップによって分割されたいくつかの小さな配列に「分割して征服」することです。 = 2 で割ると、[1, 3, 5, 7] と [2, 4, 6, 8] の 2 つの配列に分割できます (同様に、gap = 3 など)の場合、分割された配列は [1, 4, 7]、[2, 5, 8]、[3, 6] になります。) 次に、分割された配列に対して挿入ソートを実行し、各部分配列がソートされた後にそれらを削減します。ギャップ = 1 になるまで前の手順を繰り返します。つまり、挿入ソートは配列全体に対して実行されます。このとき、配列は基本的にソートされるため、移動する必要がある要素は非常に小さくなり、大規模な処理を行う場合に挿入ソートでより多くの移動が発生するという問題が解決されます。スケール配列。
具体的な例については、挿入ソートを参照してください。
ヒルソートは挿入ソートの改良版であり、データ量が多い場合には、直接挿入ソートを使用することをお勧めします。
実装コード:
次のようにコードをコピーします。
/**
* 貝殻の選別
*/
SHELL(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int の長さ = 配列の長さ;
int ギャップ = 1;
// 長さ / 3 の次のものを最初のギャップとして使用します
while (ギャップ < 長さ / 3) {
ギャップ = ギャップ * 3 + 1;
}
while (ギャップ >= 1) {
for (int i = ギャップ; i < 長さ; i++) {
T next = 配列[i];
int j = i;
while (j >= ギャップ) {
int 比較 = 配列[j - ギャップ].compareTo(next);
// すでにその位置を見つけています
if (比較 == 0 || 比較 < 0 == 昇順) {
壊す;
}
配列[j] = 配列[j - ギャップ];
j -= ギャップ;
}
if (j != i) {
配列[j] = 次へ;
}
}
ギャップ /= 3;
}
}
})
5. マージソート
マージソートは、分割統治法である再帰によって実装されます。 ソートが完了した後、2 つの配列が別々にソートされます。 "を Together に組み込む場合、マージ ソートで最も重要なことは「マージ」プロセスです。マージ プロセスでは、マージする必要がある 2 つの配列の長さと一致する追加のスペースが必要です。たとえば、指定する必要がある配列は: [3、6、8、 11] と [1, 3, 12, 15] (論理的には 2 つの配列に分割されていますが、これらの要素は実際には元の配列内にありますが、いくつかのインデックスによって 2 つの配列に分割されます。元の配列 [3, 6, 8、11、1、3、12、15 では、3 つのポインタ lo、mid、high をそれぞれ 0、3、7 に設定します。論理的なサブ配列の分割が可能です) その場合、必要な追加配列の長さは 4 + 4 = 8 となります。結合プロセスは次のように簡単に要約できます。
1) 2 つの部分配列の要素を新しい配列 copyArray にコピーします。例として、copedArray = [3, 6, 8, 11, 1, 3, 12, 15];
2) アトミック配列内の対応する最初の要素を指すように 2 つのポインターを設定します。2 つのポインターの名前が leftIdx および rightIdx であると仮定すると、leftIdx = 0 (copyedArray の最初の要素 [3] に対応)、rightIdx = 4 (コピーされた配列の 5 番目の要素 [1] に対応します)。
3) leftIdx と rightIdx が指す配列要素の値を比較し、小さい方を選択し、その値を元の配列内の対応する位置 i に割り当てます。割り当てが完了したら、その値に対して自動インクリメント操作を実行します。割り当てに参加する 2 つのインデックス leftIdx または rigthIdx の値が対応する配列の末尾に到達した場合、残るのは残りの配列要素を残りの位置に順番にコピーすることだけです。
マージの具体的な例を次に示します。
最初の旅行:
補助配列 [21, 28, 39 | 35, 38] (配列は | で区切られて左右の 2 つのサブ配列に分割されます)
[21, , , , ] (初めて 21 と 35 が比較されると、左側の部分配列が勝ちます。leftIdx = 0、i = 0)
2回目の旅行:
補助配列 [21、28、39 | 35、38]
[21, 28, , , ] (28 が 35 と 2 回目に比較されると、左側の部分配列が勝ちます。leftIdx = 1、i = 1)
3 回目の旅行: [21, 28, 39 | 35, 38]
[21, 28, 35, , ] (39 と 35 の 3 回目の比較では、右側の部分配列が勝ちます。rightIdx = 0、i = 2)
4 回目の旅行: [21, 28, 39 | 35, 38]
[21, 28, 35, 38,] (4 回目に 39 と 38 を比較すると、右側の部分配列が勝ちます。rightIdx = 1、i = 3)
5 回目の旅行: [21, 28, 39 | 35, 38]
[21, 28, 35, 38, 39] (右側のサブ配列は 5 回目にコピーされています。leftIdx = 2、i = 4 を比較する必要はありません)
上記はマージプロセスです。ソートが必要な配列全体を、長さが 1 の小さな配列に分割されるまで、限られた回数だけ分割します。長さが 1 の場合、配列をソートする必要がなくなりました。その後、これらの配列は、長さ n / 2 の最後の部分配列がマージされるまで、逆の順序でマージされます。マージが完了すると、配列のソートも完了します。
マージ ソートはすべてのソートの中で最も多くの追加スペースを必要とし、各マージにはマージに参加する 2 つの配列の長さの合計と同じ数の要素が必要です (補助配列を提供するため)。この場合、マージ ソートの空間計算量は 1 + 2 + 4 + ... + n = n * ( n + 2) / 4 であると推測できます (n のパリティ判定を無視する)。時間計算量を見積もることは困難です。 . ここでも、いくつ（）は忘れました。
実装コード:
次のようにコードをコピーします。
/**
* ソートを結合
*/
MERGE(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
this.sort(array, 0, array.length 1, ascend);
}
private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {
// 1 つを最適化する
// 部分文字列の長さが 20 未満の場合、
// 再帰呼び出しを減らすために挿入ソートを使用します
if (ハイロー < 20) {
for (int i = lo + 1; i <= hi; i++) {
T toInsert = 配列[i];
int j = i;
for (; j > lo; j) {
int 比較 = 配列[j - 1].compareTo(toInsert);
if (比較 == 0 || 比較 < 0 == 昇順) {
壊す;
}
配列[j] = 配列[j - 1];
}
配列[j] = 挿入;
}
戻る;
}
int ミッド = ロー + (ハイ ロー) / 2;
ソート(配列、ロー、ミッド、昇順);
ソート（配列、中間 + 1、こんにちは、昇順）;
マージ(配列、ロー、ミッド、ハイ、アセンド);
}
private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) {
// 2 つを最適化する
// すでに正しい順序になっている場合は、このマージをスキップします
// その必要がないので
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) {
戻る;
}
@SuppressWarnings("未チェック")
T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int lowIdx = 0;
int highIdx = ミッドロー + 1;
for (int i = lo; i <= hi; i++) {
if (lowIdx > Mid lo) {
// 左のサブ配列が使い果たされた
配列[i] = 配列コピー[highIdx++];
else if (highIdx > hi lo) {
// 右側のサブ配列が使い果たされた
配列[i] = 配列コピー[lowIdx++];
else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {
配列[i] = 配列コピー[lowIdx++];
} それ以外 {
配列[i] = 配列コピー[highIdx++];
}
}
}
})
6. クイックソート
クイック ソートは、マージ メソッドを使用して実装された「分割統治」ソート アルゴリズムでもあり、その魅力は、各パーティション (ソート アルゴリズムの核心) の最終的な正しいソート位置を (1 回で) 決定できることです。位置決めが正確な場合、この要素は次のサイクルでは考慮されません)。