1. 概要
ソートと検索はプログラミングにおける 2 つの非常に基本的な問題であり、これら 2 つのタイプの問題を解決するために使用される古典的なアルゴリズムが数多くあります。この記事では、出発点として役立つことを期待して、主に Java でのソート アルゴリズムの実装についての基本的な説明を行います。役割。その前に、まずいくつか質問させてください。正しいクイック ソートを作成できますか?クイックソートが実際に高速になるのはどのような状況ですか?クイックキューは十分に速いですか?さらに最適化することはできますか?これらの質問を踏まえて、jre7 でクイックソートがどのように実装されているかを見てみましょう。
JRe7 のソートの実装クラスは DualPivotQuickSort.java です。 jre6 と比較すると、主に 2 か所が変更されています。1 つは挿入ソートの実装で、もう 1 つは QuickSort 実装のピボットが 1 つから 2 つに変更されています。 。 int 型の配列を例に挙げます。このクラスには、ソート実装のためのコア メソッドがあります。このメソッドのプロトタイプは次のとおりです。
次のようにコードをコピーします。
void sort(int[] a, int left, int right, boolean leftmost)
パラメータ a は並べ替える必要がある配列、left は並べ替える必要がある配列範囲の左端の要素のインデックスを表し、right は範囲の右端の要素のインデックスを表し、leftmost は範囲が左端かどうかを表します。配列内の範囲。例えば：
配列: [2, 4, 8, 5, 6, 3, 0, -3, 9] は 3 つの区間 (2, 4, 8){5, 6}<3, 0, -3, 9> に分割できます。
() 間隔の場合、左 = 0、右 = 2、左端 = true
{} 間隔、left=3、right=4、leftmost=false の場合、<> 間隔の対応するパラメータを同じ方法で取得できます。
間隔の長さが 47 未満の場合、このメソッドは挿入ソートを使用します。それ以外の場合は、クイック ソートが使用されます。
2. 挿入ソートの実装
左端が true の場合、従来の挿入ソートが使用され、コードはカードをプレイするときのカードの取得と挿入に似ています。
次のようにコードをコピーします。
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
壊す;
}
}
a[j + 1] = ai;
}
従来の挿入ソート コード
左端が false の場合、新しいタイプの挿入ソート (ペア挿入ソート) が使用されます。改善点は、以前にソートされた配列を走査するたびに 2 つの要素を挿入する必要があるのに対し、従来の挿入ソートでは適切な場所を見つけるだけで済むことです。挿入する要素。挿入ソートの場合、重要なのは、挿入される要素に適した挿入位置を見つけることです。この位置を見つけるには、以前にソートされた部分配列を走査する必要があるため、挿入ソートの場合は、ソート全体で要素を走査します。プロセス数によってパフォーマンスが決まります。明らかに、各走査に 2 つの要素を挿入すると、並べ替えプロセス中に走査される要素の数を減らすことができます。実装コードは次のとおりです。
次のようにコードをコピーします。
for (int k = left; ++left <= right; k = ++left) {
int a1 = a[k]、a2 = a[左];
if (a1 < a2) {
a2 = a1; a1 = a[左];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
}
a[++k + 1] = a1;
while (a2 < a[--k]) {
a[k + 1] = a[k];
}
a[k + 1] = a2;
}
ここで疑問が生じます。なぜ左端の範囲では従来の挿入ソートが使用され、他の範囲ではペアごとの挿入ソートが使用されるのでしょうか。従来の挿入ソート コードを上記のペアごとの挿入ソート コードに置き換えると、どのような問題が発生しますか?皆さんもぜひご自身で答えていただければと思います。 。 。
3. クイックソートの実装
JRe7 ではクイック ソートも改善されました。従来のクイック ソートはピボットを選択します (jre6 のピボットの選択方法は、配列の左端、中央、右端の位置にある要素を選択し、中央の値を持つ要素をランク付けします)。ピボット)、両端から中央までトラバースし、左のトラバース中に遭遇したオブジェクトを置きますピボットより大きい値は、右側のトラバーサルで検出されたピボット以下の値と交換され、ピボットの値が挿入されます。これにより、ピボットの左側の値が以下になります。 pivot と等しく、pivot の右側の値が pivot より大きいです; continue 次に、再帰を使用して左側と右側をそれぞれソートします。
上記の分析を通じて、次のことがわかります。挿入ソートの各ステップは配列のサブ範囲を絶対順序付けすることであり、各サイクルの本質はこのサブ範囲を継続的に拡張することであるため、最適化の方向は次のとおりであることがわかります。 make 各ループの走査によりサブ範囲ができるだけ早く拡張されるため、走査ごとに 1 つの要素を挿入する上記の最適化が、一度に 2 つの要素を挿入するように最適化されます。もちろん、なぜこの数字をもっと大きくしないのかと疑問に思う人もいるでしょう。たとえば、横断するたびに 5 または 10 が挿入されます。 。 。明らかに、これは不可能です。走査するたびに n 個の項目 (n は配列の長さ) を挿入することになります。 。 。その理由については、誰もが自分で答えることができます。
クイック ソートの場合、各再帰は、完全に順序付けされるのではなく、並べ替えが必要なサブ範囲をより順序付けすることを目的としています。そのため、クイック ソートのパフォーマンスは、各再帰操作によってサブ範囲がどのように順序付けされるかによって決まります。部分区間がどの程度順序付けされるかを決定するのは、もちろん再帰の回数です。部分間隔を比較的規則的にするための素早い並べ替えの鍵はピボットであるため、最適化の方向もピボットにする必要があります。次に、ピボットの数を増やしても、ピボットの数には影響しないことがわかります。再帰には大きな影響があり、場合によっては再帰の数が減る場合もあります。挿入ソートと同様の質問は、ピボットの数をどれだけ増やす必要があるかということです。明らかに、ピボットの値は大きすぎることはできません。最適化にはコストがかかり、ピボットを増やすコストは要素の位置を毎回交換するプロセスに隠れていることに注意してください。 Guanziはちょっと売れすぎな気がします。 。 。ピボット値が 2 の場合に迅速な並べ替えがどのように実装されるかを見てみましょう。実際、その実装プロセスを理解するのは難しくありません。
1. まず 2 つのピボットを選択します。ピボットの選択方法は、配列を同じ長さの 6 つのセグメントに分割し、5 つの要素を小さい要素から大きい要素に並べ替えて、2 番目の要素を取り出します。 4 番目のものは、それぞれ pivot1 と pivot2 です。
2. ピボットを選択した後、左端と右端から中央までトラバースします。左のトラバースの停止条件は、pivot1 以上の値に達し、その位置を右のトラバースの停止条件としてマークします。トラバーサルとは、pivot2 の値以下の値を検出し、その位置を偉大なものとしてマークすることです。
3. 次に、小さい位置から後方に移動します。移動した位置は k で表されます。
a. k 位置の値が pivot1 より小さい場合、k 位置とless 位置の値を交換し、less の値に 1 を加算します。これにより、値が pivot1 の左側になります。 less 位置が pivot1 より小さく、less 位置と k 位置の間の値が pivot1 以上になります
b. 位置 k の値が pivot2 より大きい場合、その大きい位置から左に移動します。この値が pivot1 より小さい場合は、移動の停止条件となります。この値をlessの位置に書き込み、その値をkの位置として書き込み、kの位置の値をgreatの位置として書き込み、最後にless++、great--;を追加します。 pivot1 以上になるように、k 位置と Great 位置を交換してから、great-
4. 上記のプロセスが完了すると、ソートされたサブ間隔が 3 つのセグメント (<pivot1, pivot1<=&&<=pivot2,>pivot2) に分割されます。最後に、これら 3 つのセグメントに対して再帰が使用されます。
次のようにコードをコピーします。
/*
*パーティショニング:
*
・左部分 中央部分 右部分
* +------------------------------------------------ ---------------+
* | < ピボット 1 <= && <= ピボット 2 |
* +------------------------------------------------ ---------------+
* ^ ^ ^
* |
* 少ない k 素晴らしい
*
*不変条件:
*
* オールイン (左、以下) < pivot1
* pivot1 <= オールイン [less, k) <= pivot2
* オールイン (素晴らしい、正しい) > pivot2
*
※ポインタkは?部分の最初のインデックスです。
*/
JRe7でのソート実装の核心的な内容は上記の通りです。具体的な内容については、該当クラスのコードを参照していただき、誤りや不備があれば修正してください。