Java ソートアルゴリズムについてどれくらい知っていますか?

今日は、Java のさまざまなソートアルゴリズムについてお話します。以前、上級開発者との面接があり、九九の表に関する質問を受けたからです。読み手の答えを聞いて、すぐに意味がわかりました。少し誤解を招くような気がしましたが、実際には、面接官はソートアルゴリズムをテストしたかったのです。そうでなければ、本当に退屈だったかもしれません。

ソートアルゴリズム

ソートアルゴリズムとは何でしょうか。実のところ、これについてはあまり説明する必要はありません。意味を明確にするだけで十分です。ソートとは、1 つ以上のキーワードのサイズに応じて、一連のレコードを昇順または降順に並べる操作です。

ソートアルゴリズムには多くの種類があります。ソートアルゴリズムによって、時間と空間の効率の点で長所と短所が異なります。時間と空間をトレードするアルゴリズムもあれば、時間と空間をトレードするアルゴリズムもあります。今日は、それらを 1 つずつリストします。

バブルソート

バブルソートとは何ですか?

バブルソートは、隣接する 2 つの数字を順番に比較し、小さい数字を前に、大きい数字を後ろに配置します。

まるで泡のように、一つずつ泡が上がっていきます。

バブルソートは、隣接する 2 つの数字を順番に比較し、小さい数字を前に、大きい数字を後ろに配置します。

実際、比較プロセスは次のようになります。

最初の比較:

まず、最初の数字と 2 番目の数字を比較し、小さい方の数字を前に、大きい方の数字を後ろに置きます。次に、2 番目の数字と 3 番目の数字を比較し、小さい方の数字を前に、大きい方の数字を後ろに置き、最後まで比較を続けます。最後に、最大の数字が配置されます。

2番目の比較:

まず、最初の数字と 2 番目の数字を比較し、小さい方の数字を前に、大きい方の数字を後ろに置き、最後から 2 番目の数字と比較し、2 回目の比較を終了します。このように、最後の位置の数字が最大になり、最後から 2 番目の位置の数字が 2 番目に大きくなります。

そして、このように実行を続けます。3 回目は 3 番目の数字を取得します。これは誰でも理解できます。ソートするシーケンスの数が n であると仮定すると、ソートを完了するには n-1 ラウンドかかります。最初のラウンドでは比較回数は n-1 で、その後の各ラウンドでは 1 ずつ減少します。

コードを使用して実装してみましょう。

公共 静的void main( int []a){
整数 温度;
        //N-1回の比較が必要
( int i = 0; i < a.length-1; i++) {
            //a.length-i-1 によれば、各ラウンドで必要な比較の回数はラウンドごとに 1 ずつ減少します。
 ( int j = 0; j < a.length-i-1; j++)の場合{
                //隣接する数値を比較し、条件を満たす場合は置き換えます
                もし(a[j] > a[j+1])であれば{
温度= a[j];
                    a[j] = a[j+1];
                    a[j+1] =温度;
                }
            }
        }
    }

挿入ソート

挿入ソートには多くの種類がある

直接挿入ソート
バイナリ挿入ソート
シェルソート

これらのソート方法はすべて挿入ソートです。

まず、直接挿入ソートを見てみましょう。

比較プロセスは次のようになります。配列内の 2 番目のデータが前方比較されます。つまり、2 番目の数値が先頭のその前の数値と比較され、条件が満たされた場合は、それらが交換されます。
配列が与えられ、それを小さいものから大きいものの順に並べ替えたいとします。配列は [3,1,4,6,5,17,12,11] です。このとき、最初のステップは 1 と 3 を比較することです。1 が 3 より小さい場合は、1 と 3 の位置を入れ替えて [1,3,4,6,5,17,12,11] にします。

次に、3 番目の数字を 2 番目の数字と比較し、一致する場合は交換します。ただし、ここでは前方比較を続ける必要があります。つまり、4 と 3 と 1 をそれぞれ比較し、このプロセスを繰り返す必要があります。すべてのデータが整理されると、必要な結果が得られます。どのような結果になるか確認するために、いくつかコードを書いてみましょう。

公共 静的void基底( int []配列){
 // 2番目の項目から開始
    配列 == null || 配列の長さ < 2 の場合 {
戻る;
        }
 ( int i = 1; i < 配列の長さ; i++) {
 int cur = 配列[i];
            // 挿入される数字が最小にならないようにするための cur ランディング マーク
            ブールフラグ = false ;
            // 逆順にトラバースし、シフトを続ける
( int j = i - 1; j > -1; j --) {  
                （cur < 配列[j]）の場合{
                    配列[j + 1] = 配列[j];
                }それ以外{
                    配列[j + 1] = cur;
                    フラグ = true ;
                    壊す;
                }
            }
            if (!フラグ) {
             配列[0] = cur;
            }
        }
    }
 }

挿入ソートには多くの方法があると前に述べたので、他の挿入ソートについても説明し、それらの違いを確認する必要があります。同意しますか?

先ほど、ソートするたびに配列をシフトする必要があると言いましたが、これまでの判断条件は最適化することができます。この最適化により、さまざまな挿入ソートが生まれました。次に、このバイナリ検索挿入ソートを見てみましょう。

バイナリ検索挿入ソート

直接挿入ソートを最適化する際の核心は、現在の数値を挿入する位置を素早く見つけることです。順序付けられた配列内で特定の値を見つける最も速い方法は、間違いなくバイナリ検索です。少なくともAh Fanの考えでは、最適化を考えるとき、最初の選択肢はバイナリ検索を使用できるかどうかです。

まずコードの実装を見て、次にその欠点と、多くの人がバイナリ検索と挿入ソートを使用しない理由を見てみましょう。

 // システムに組み込まれたバイナリ検索法を使用して挿入位置を特定します
     // 不安定なソート
公共 静的void最適化( int []配列){
        配列 == null || 配列の長さ < 2 の場合 {
戻る;
        }
 for ( int i = 1; i < array.length; i++) { int cur = array[i];
 int [] sorted = Arrays.copyOf(配列、i);
整数 インデックス= Arrays.binarySearch(sorted,cur);インデックス< 0 の場合 {
インデックス= -(インデックス+ 1 );
          }
 ( int j = i - 1; j >インデックス- 1; j --) {  
               配列[j + 1] = 配列[j];
           }
           配列[インデックス] = cur;
        }
   }

その中で、Ah Fen はシステム独自の配列を使用して、バイナリ検索と挿入ソートを実行しました。なぜでしょうか? JDK では、Arrays.binarySearch() が提供されています。実装するには、メソッドの入力パラメータに順序付けされた配列を渡す必要があります。なぜこのメソッドを使用しないのでしょうか?

ソート前には 2 つの数字が同じであっても、ソート後には順序が変わる場合があり、ソートアルゴリズムが不安定であることを意味します。これを安定と呼びます。

このような不安定なソートがあるのなら、安定したソートもあるべきではないでしょうか。はい、あります。では、安定したソートとは何でしょうか。はい、その通りです。バブルソートは安定したソートです。なぜなら、バブルソートはサイズが要件を満たさない場合にのみ、隣接する要素の位置を交換するからです。同じ要素の相対的な順序は変更しないため、安定したソートアルゴリズムです。

先ほど、このソートにはシェルソートがあると言いましたので、シェルソートについて見てみましょう。

シェルソート

正直に言うと、このソートを初めて知ったとき、ヒルという人物によって改良されたのかと思いました。結果、確かにそうであることがわかりました。シェルソートは、((縮小増分ソート)とも呼ばれ、1959 年に提案した DLShell にちなんで名付けられました。実際には、シェルのソートと呼ぶべきものです。

シェルソートは、まずソートするレコードのシーケンス全体をいくつかのサブシーケンスに分割し、それらを個別に直接挿入してソートします。シーケンス全体のレコードが「基本的に順序付けられている」場合、すべてのレコードが直接挿入され、順番にソートされます。

実際には、最初に単純なグループ化を実行し、ソートする配列をステップサイズのギャップに従ってグループ化し、次に直接挿入ソート方式を使用して各グループの要素をソートするのと同じです。ギャップが半分に縮小されるたびに、上記の操作が繰り返されます。ギャップ = 1 の場合、直接挿入を使用してソートが完了します。

コードの実装は次のようになります

公共 静的voidソート( int []a){
長さ = a.length;
整数h = 1;
    ただし、(h < 長さ / 3) h = 3 * h + 1 です。
 (; h >= 1; h /= 3)の場合{
 ( int i = 0; i < a.length - h; i += h) {
 ( int j = i + h; j > 0; j -= h)の場合{
                もし(a[j] < a[j - h])であれば{
整数 温度= a[j];
                    a[j] = a[j - h];
                    a[j - h] =温度;
                }
            }
        }
    }
 }

選択ソート

選択ソートはシンプルで直感的なソートアルゴリズムです。

これは比較的簡単です。その理由は、ソートされていないシーケンスから最小または最大の要素を直接見つけ、それをソートされたシーケンスの開始位置に格納し、次に残りのソートされていない要素から最小 (大きい) 要素を探し続けて、それをソートされたシーケンスの末尾に配置するからです。すべての要素がソートされるまでこれを繰り返します。

実際、概念的にはバブルソートに少し似ていますが、異なります。

コードが実装されているかどうか確認してみましょう:

公共 静的voidソート( int []a){
 ( int i = 0; i < a.length; i++) {
整数 最小値= i;
        //ソートする中央値が最小の位置を選択する
( int j = i + 1; j < a.length; j++) {
            もし(a[j] < a[ min ])であれば
最小値= j;
            }
        }
        //最小値が現在の値と等しくない場合はスワップする
        もし（最小値！＝i）{
整数  temp = a[i];
            a[i] = a[最小値];
            a[分] =温度;
        }
    }
 }