Java で実装されたいくつかの一般的なソートアルゴリズムの詳細な解釈

ソートアルゴリズムはさまざまな場所で使用されています。最近、そのアルゴリズムを読み直し、自分で簡単に実装しました。将来のレビューのために資料として残しておくために、ここに記録しておきます。

では、これ以上長々とせずに、古典的なソートアルゴリズムを 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 が徐々に増加する）、比較の回数はどんどん少なくなりますが、配列が最初に順序付けられているかどうかに関係なく、選択ソートは i から配列の最後まで選択比較を実行するため、特定の長さの配列の場合、選択ソートの比較回数は固定です：1 + 2 + 3 + …. + n = n * (n + 1) / 2、交換回数は初期配列の順序によって異なります。初期配列順序がランダムである場合、最悪の場合、配列要素は n 回交換され、最良の場合（配列自体は順序付けられている）は 0 回になる可能性があります。

このことから、選択ソートの時間計算量と空間計算量はそれぞれ O(n2) と O(1) であると推測できます (選択ソートでは、配列要素を交換するための追加のスペースのみが必要です)。

実装コード:

 /**
 * 選択ソート
 */  
選択(新しいソート可能() { 
    パブリック<T はComparable<T>>を拡張しますvoid sort(T[] 配列、ブール値の昇順) { 
         int len ​​= 配列.長さ; 
         ( int i = 0 ; i < len; i++) { 
            選択されたint = i; 
             ( int j = i + 1 ; j < len; j++) { 
                 int compare = 配列[j].compareTo(配列[選択]); 
                 if (比較!= 0 && 比較< 0 == 昇順) {
                    選択された = j;
                }
            } 
 
            exchange(配列、i、選択されたもの);
        }
    }
 })

2. 挿入ソート

挿入ソートの基本的な考え方は、配列をトラバースする過程で、シリアル番号 i の前の要素、つまり [0..i-1] がソートされていると想定することです。このトリップでは、i に対応する要素 x の正しい位置 k を見つける必要があり、この位置 k を見つける過程で、比較する要素を 1 つずつ 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 ] 
 
 1回目のパス: [ 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) です。

実装コード:

 /**
 * 挿入ソート
 */  
挿入(新しいSortable() { 
    パブリック<T はComparable<T>>を拡張しますvoid sort(T[] 配列、ブール値の昇順) { 
         int len ​​= 配列.長さ; 
         ( int i = 1 ; i < len; i++) {
            T toInsert = 配列[i]; 
            整数j = i; 
             (; j > 0 ; j--)の場合{ 
                 int compare = 配列[j - 1 ].compareTo(toInsert); 
                 if (比較 == 0 || 比較 < 0 == 昇順) { 
                    壊す;
                }
                配列[j] = 配列[j - 1 ];
            } 
 
            配列[j] = toInsert;
        }
    }
 })

3. バブルソート

バブルソートは、最も古典的なソートアルゴリズムとみなすことができます。これは、学生時代に初めて触れたアルゴリズムだったことを覚えています。実装方法が最も単純で、2層のforループを使用しているためです。内側のループでは、隣接する2つの要素が逆順になっているかどうかを判断します。逆順になっている場合は、2つの要素を交換します。外側のループを1回実行すると、配列の残りの要素のうち最小の要素を「フロート」して前に配置できるため、バブルソートと呼ばれています。

簡単な例を見てみましょう。

   
 
初期状態: [ 24 , 19 , 26 , 39 , 36 , 7 , 31 , 29 , 38 , 23 ] 
 
内側の第1パス: [ 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 ] ( 3番目 [ 7 ] <-> 2番目 [ 26 ] ) 
 
内側の8番目のパス：[ 24 、 7 、 19 、 26 、 39 、 36 、 23 、 31 、 29 、 38 ] （2番目 [ 7 ] <-> 1番目 [ 19 ] ） 
 
 9番目の内側のトリップ: [ 7 、 24 、 19 、 26 、 39 、 36 、 23 、 31 、 29 、 38 ] ( 1番目 [ 7 ] <-> 0番目 [ 24 ] ) 
 
 ………

実際、バブルソートは選択ソートと非常によく似ています。比較回数は同じで、n * (n + 1) / 2です。ただし、バブルソートは最小値を選択する過程で追加の交換を実行します（バブルソートは、ソート中に隣接する要素の順序が間違っていることが判明した場合、隣接する要素を交換します。対応する選択ソートは、内部ループの比較が完了した後の状況に応じてのみ、交換するかどうかを決定します）。したがって、私の意見では、選択ソートはバブルソートの改良版です。

実装コード:

 /**
 * バブルソートは挿入ソートに非常に似ています
 */  
バブル(新しいソート可能() { 
    パブリック<T はComparable<T>>を拡張しますvoid sort(T[] 配列、ブール値の昇順) { 
         int長さ = 配列.長さ; 
        最後の交換ID = 0 ; 
         ( int i = 0 ; i < 長さ; i++) { 
             // 交換が行われたかどうかを識別するためのフラグを false にマークします 
            ブール値isExchanged = false ; 
             // 最後の比較と交換はインデックス i に到達する前に発生しました 
             int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i; 
             ( int j = length - 1 ; j > currOrderedIdx; j--) { 
                 int compare = 配列[j - 1 ].compareTo(配列[j]); 
                 if (比較!= 0 && 比較> 0 == 昇順) {
                    交換(配列、j - 1 、j);
                    isExchanged = true ;
                    最後の交換ID = j;
                }
            } 
             // 交換が行われない場合は、配列がすでに整列していることを意味します 
             if (isExchanged == false ) { 
                壊す;
            }
        }
    }
 })

4. シェルソート

シェル ソートが誕生したのは、挿入ソートでは大きな配列を処理するときに移動しなければならない要素が多すぎるという問題に遭遇したためです。ヒルソートの考え方は、大きな配列をギャップで分割されたいくつかの小さな配列に「分割して征服する」ことです。たとえば、配列[1、2、3、4、5、6、7、8]は、ギャップ= 2で分割すると、[1、3、5、7]と[2、4、6、8]の2つの配列に分割できます（同様に、ギャップ= 3の場合、分割された配列は[1、4、7]、[2、5、8]、[3、6]です）。次に、分割された配列に対してそれぞれ挿入ソートを実行します。各サブ配列がソートされた後、ギャップ値が減らされ、ギャップ= 1になるまで、つまり配列全体が挿入されてソートされるまで、前の手順が繰り返されます。この時点で、配列は基本的にソートされているため、移動する必要がある要素は非常に小さくなり、挿入ソートが大きな配列を処理するときに移動回数が多いという問題が解決されます。

具体的な例については、挿入ソートを参照してください。

シェルソートは挿入ソートの改良版です。データ量が多い場合の効率向上に非常に役立ちます。データ量が少ない場合は、挿入ソートを直接使用することをお勧めします。

実装コード:

 /**
 * 貝殻の選別
 */  
 SHELL(新しいソート可能() { 
    パブリック<T はComparable<T>>を拡張しますvoid sort(T[] 配列、ブール値の昇順) { 
         int長さ = 配列.長さ; 
        ギャップ= 1 ; 
 
         // 長さ/3の次に大きいものを最初のギャップとして使用します 
         （ギャップ<長さ/ 3 ）{
            ギャップ = ギャップ * 3 + 1 ;
        } 
 
        ギャップ >= 1の場合
             ( int i = ギャップ; i < 長さ; i++) {
                T next = 配列[i]; 
                整数j = i; 
                 (j >= ギャップ) { 
                     int compare = 配列[j - ギャップ].compareTo(next); 
                     // すでに位置が見つかりました 
                     if (比較 == 0 || 比較 < 0 == 昇順) { 
                        壊す;
                    } 
 
                    配列[j] = 配列[j - ギャップ];
                    j -= ギャップ;
                } 
                もし(j != i) {
                    配列[j] = 次;
                }
            }
            ギャップ /= 3 ;
        } 
 
    }
 })

5. マージソート

マージは、「分裂と征服」のカテゴリに属し、2つの並べ替えが完了した後、2つの並べ替えのように並べ替えます[3、6、8、11]および[1、3、12、15]は指定されていますが、これらの要素は実際には元の配列に分割されていますが、元のアレイは[3、8、11、1、3、12、15を除いて、3つのポインターを設定します必要な配列は4 + 4 = 8です。マージプロセスは、次のように簡単にまとめることができます。

1) 2 つのサブ配列の要素を新しい配列 copyedArray にコピーします。上記の例では、copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] となります。

2) アトミック配列の最初の要素を指すように2つのポインタを設定します。2つのポインタの名前がleftIdxとrightIdxであると仮定すると、leftIdx = 0（copytedArray [3]の最初の要素に対応）、rightIdx = 4（copytedArray [1]の5番目の要素に対応）となります。

3) leftIdx と rightIdx が指す配列要素の値を比較し、小さい方を選択して、その値を元の配列の対応する位置 i に割り当てます。割り当てが完了すると、割り当てに関係する 2 つのインデックスが 1 ずつ増加します。leftIdx または rightIdx の値が対応する配列の末尾に達した場合は、配列の残りの要素を残りの位置に順番にコピーするだけです。

マージの具体的な例を以下に示します。

 ***旅行： 
 
補助配列 [ 21 , 28 , 39 | 35 , 38 ] (配列は|で区切られた左と右の2つのサブ配列に分割されます) 
 
 [ 21 、 、 、 ] （最初に21と35を比較すると、左のサブ配列が勝ち、 leftIdx = 0 、 i = 0 ） 
 
 2回目の旅行: 
 
補助配列 [ 21 , 28 , 39 | 35 , 38 ] 
 
 [ 21 , 28 , , , ] （2回目に28と35を比較すると、左のサブ配列が勝ち、 leftIdx = 1 、 i = 1 ） 
 
 3回目の旅行: [ 21 、 28 、 39 | 35 、 38 ] 
 
 [ 21 、 28 、 35 、 、 ] （3回目に39と35を比較すると、右のサブ配列が勝ち、 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 回につき 2 つ) 分割して、長さ 1 の小さな配列に分割することができます。長さが 1 になると、配列をソートする必要がなくなります。その後、配列は逆の順序で（再帰の使用により）マージされ、長さ n/2 の最後のサブ配列がマージされます。マージが完了すると、配列のソートも完了します。

マージ ソートは、すべてのソートの中で最も多くの追加スペースを必要とします。各マージには、マージに関係する 2 つの配列の長さの合計と同じ数の要素が必要です (補助配列を提供するため)。マージソートの空間計算量は 1 + 2 + 4 + … + n = n * ( n + 2) / 4 (n の偶奇性を無視) であると推測できます。時間計算量は見積もるのが難しく、それが何だったか忘れてしまいました (囧)。

実装コード:

 /**
 * マージソート
 */  
 MERGE(新しいソート可能() { 
    パブリック<T はComparable<T>>を拡張しますvoid sort(T[] 配列、ブール値の昇順) { 
         this .sort(配列、 0 、配列の長さ - 1 、昇順);
    } 
 
    プライベート<T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) { 
         // 1つを最適化 
         // 部分文字列の長さが20未満の場合、  
         // 挿入ソートを使用して再帰呼び出しを減らす 
         (高 - 低 < 20 )の場合{ 
             ( int i = lo + 1 ; i <= hi; i++) {
                T toInsert = 配列[i]; 
                整数j = i; 
                 (; j > lo; j--)の場合{ 
                     int compare = 配列[j - 1 ].compareTo(toInsert); 
                     if (比較 == 0 || 比較 < 0 == 昇順) { 
                        壊す;
                    }
                    配列[j] = 配列[j - 1 ];
                } 
 
                配列[j] = toInsert;
            } 
 
            戻る;
        } 
 
         int mid = lo + (hi - lo) / 2 ;
        ソート(配列、lo、mid、ascend);
        ソート(配列、mid + 1 、hi、ascend);
        マージ(配列、lo、mid、hi、ascend);
    } 
 
    プライベート<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 ]); 
         （leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend）の場合{ 
            戻る;
        } 
 
         @SuppressWarnings ( "チェックなし" )
        T[]配列コピー = (T[])新しいComparable[hi - lo + 1 ];
        System.arraycopy(配列、lo、arrayCopy、 0 、arrayCopy.length); 
 
        整数lowIdx = 0 ; 
         int highIdx = mid - lo + 1 ; 
 
         ( int i = lo; i <= hi; i++) { 
             (lowIdx > mid - lo)の場合{ 
                 // 左のサブ配列が使い果たされました 
                配列[i] = 配列コピー[highIdx++];
            }それ以外  (highIdx > hi - lo)の場合{ 
                 // 右サブ配列が使い果たされました 
                配列[i] = 配列コピー[lowIdx++];
            }それ以外  （arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend）の場合{
                配列[i] = 配列コピー[lowIdx++];
            }それ以外{
                配列[i] = 配列コピー[highIdx++];
            }
        }
    }
 })

6. クイックソート

クイックソートも、マージメソッドによって実装された「分割統治」ソートアルゴリズムです。その魅力は、各パーティション内の配列要素の最終的な正しいソート位置を決定できることにあります（ソートアルゴリズムの核心）（一度正確に配置できれば、この要素は次のループでは考慮されません）。

オリジナルリンク: http://easense2009.iteye.com/blog/1568614