ソートアルゴリズムのより詳細な概要

ソートアルゴリズム	平均時間計算量
バブルソート	（n2）
選択ソート	（n2）
挿入ソート	（n2）
シェルソート	O(n1.5)
クイックソート	O(N*logN)
マージソート	O(N*logN)
ヒープソート	O(N*logN)
基数ソート	O(d(n+r))

1. バブルソート

基本的な考え方: 2 つの数値を比較すると、大きい数値は下がり、小さい数値は上がります。
プロセス：
- 隣接する 2 つのデータを比較し、2 番目の数値が小さい場合は、それらの位置を交換します。
- 最初の 2 つのデータが比較されるまで、後ろから前に向かって 2 つずつ比較します。最後に、最小の数字を開始位置に交換し、最後の最小の数字の位置が配置されるようにします。
- 上記の手順を繰り返し、2.3...n-1番目に小さい数字を順番に並べます。
  バブルソート
平均時間計算量: O(n2)

Java コードの実装:

公共 静的  voidバブルソート( int [] arr){ 
 
 int temp; //一時変数 
 for ( int i= 0 ; i<arr.length- 1 ; i++){ // 合計 arr.length-1 回の移動回数を示します。  
 ( int j = arr.length - 1 ; j>i; j--) { 
 
 (arr[j] < arr[j- 1 ])の場合{
                 temp = arr[j];
                 arr[j] = arr[j- 1 ];
                 arr[j- 1 ] = 一時;
             }
         }
     }
 }

最適化：

問題について：
データがソートされた後、バブルアルゴリズムは arr.length-1 回まで次の比較ラウンドを継続し、それ以降の比較は無意味になります。

プラン：
フラグを設定します。交換が発生した場合、フラグは true に設定され、交換が発生しない場合は、フラグは false に設定されます。
このように、比較ラウンドの後にフラグがまだ false の場合、つまり、このラウンドで交換が発生しない場合は、データがソートされており、続行する必要がないことを意味します。

公共 静的  voidバブルソート1( int [] arr){ 
 
 int temp; //一時変数 
 boolean flag; //フラグを交換するかどうか 
 for ( int i= 0 ; i<arr.length- 1 ; i++){ // 合計 arr.length-1 回の移動回数を示します。   
 
       フラグ = false ;
 ( int j = arr.length - 1 ; j>i; j--) { 
 
 (arr[j] < arr[j- 1 ])の場合{
               temp = arr[j];
               arr[j] = arr[j- 1 ];
               arr[j- 1 ] = 一時;
               フラグ = true ;
           }
       }
 if (!flag) break ;
   }
 }

2. 選択ソート（SelectionSort）

基本的な考え方:
長さ N の順序付けられていない配列で、最初に n-1 個の数値を走査し、最小値を見つけて最初の要素と交換します。
もう一度 n-2 個の数を走査し、最小値を見つけて 2 番目の要素と交換します。
。。。
n-1 回目のトラバーサルで、最小の値を見つけて n-1 番目の要素と交換すると、ソートが完了します。
プロセス：
選択ソート
平均時間計算量: O(n2)

Java コードの実装:

公共 静的  void select_sort( int配列[], int長さ){ 
 
 ( int i = 0 ; i < 長さ - 1 ; i++ ) { 
 
最小インデックス = i;
 ( int j = i + 1 ; j < 長さ; j++ ) {
 （配列[j]<配列[最小インデックス]）{
              最小インデックス = j;
          }
       }
 （最小インデックス!= i）の場合{
 int temp = 配列[i];
           配列[i] = 配列[最小インデックス];
           配列[最小インデックス] = temp;
       }
   }
 }

3. 挿入ソート

基本的な考え方:
ソートする数値のセットでは、最初の n-1 個の数値がすでにソートされていると仮定し、前の順序付けられたシーケンスに n 番目の数値を挿入して、これらの n 個の数値もソートされるようにします。すべてが正常になるまでこのサイクルが繰り返されます。
プロセス：
挿入ソート
同じシーン
平均時間計算量: O(n2)

Java コードの実装:

公共 静的  void insert_sort( int配列[], int長さ){ 
 
整数温度; 
 
 ( int i = 0 ; i < 長さ - 1 ; i++) {
 ( int j = i + 1 ; j > 0 ; j--) {
 （配列[j] < 配列[j- 1 ]）の場合{
               temp = 配列[j- 1 ];
               配列[j- 1 ] = 配列[j];
               配列[j] = temp;
           } else { // スワップする必要はありません 
壊す;
           }
       }
   }
 }

4. シェルソート

序文：
データシーケンス 1: 13-17-20-42-28。挿入ソートを使用した場合、13-17-20-28-42。スワップ回数: 1;
データシーケンス 2: 13-17-20-42-14 挿入ソートを使用、13-14-17-20-42。スワップ回数: 3;
データシーケンスが基本的に順序付けられている場合は、挿入ソートを使用する方が効率的です。
基本的な考え方:
ソートする数値セットを一定の増分に従って複数の部分列に分割し、部分列を個別に挿入してソートします。
その後、徐々に増分を減らして、上記のプロセスを繰り返します。増分が 1 になるまでは、基本的にデータ列を順序付けし、挿入ソートを実行します。
プロセス：
シェルソート
平均時間計算量:

Java コードの実装:

公共 静的  void shell_sort( int配列[], int長さ){ 
 
整数温度 = 0 ;
 int増分 = 長さ; 
 
 （真）の間{
       増加 = 増加 / 2 ; 
 
 for ( int k = 0 ;k<incre;k++){ //増分に応じていくつかのサブシーケンスに分割します  
 
 ( int i=k+incre;i<lenth;i+=incre)の場合{ 
 
 ( int j=i;j>k;j-=incre)の場合{
 （配列[j]<配列[j-incre]）の場合{
                       temp = 配列[j-incre];
                       配列[j-incre] = 配列[j];
                       配列[j] = temp;
                   }それ以外{
壊す;
                   }
               }
           }
       } 
 
 （増分 == 1 ）の場合{
壊す;
       }
   }
 }

5. クイックソート

基本的な考え方: (分割統治)
- まず、シーケンスから数字をキー値として取得します。
- この数字より小さい数字はすべて左側に置き、この数字より大きいか等しい数字はすべて右側に置きます。
- 各間隔に数字が 1 つだけになるまで、左側と右側の 2 つの小数点シリーズに対して 2 番目の手順を繰り返します。
理解を助ける：穴を掘って数字を埋める
- 最初は i = 0、j = 9、キー = 72
  a[0]の数字がkeyに保存されているので、配列a[0]に穴が掘られていると理解でき、ここに他のデータを埋め込むことができます。
  j から始めて、キーより小さい数字を探します。 j=8のとき、条件が満たされ、a[0] = a[8]; i++; a[8]を掘り出し、前のピットa[0]に埋めます。
  このようにすると、ピットa[0]は解決されますが、新しいピットa[8]が形成されます。どうすればよいでしょうか?簡単です。穴a[8]を埋める数字を見つけるだけです。
  今回は、iから始めて、keyより大きい数字を後ろ向きに探します。i=3のとき、条件が満たされ、a[8] = a[3]; j--; a[3]を掘り出して、前のピットに埋めます。
```
配列: 72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
 0 1 2 3 4 5 6 7 8 9
```
- 今、i = 3; j = 7; キー = 72
  上記の手順を繰り返し、最初に後ろから前へ、次に前から後ろへ検索します。
  jから始めて前方に検索します。j=5のとき、条件が満たされます。a[5]を掘り出して、前のピットに埋めます。a[3] = a[5]; i++;
  i から検索を開始し、逆方向に進みます。i=5 のとき、i==j なので終了します。
  このとき、i = j = 5であり、a[5]はたまたま前回掘った穴なので、鍵はa[5]に埋め込まれます。
```
配列: 48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
 0 1 2 3 4 5 6 7 8 9
```
- a[5]の前の数字はそれより小さく、a[5]の後の数字はそれより大きいことがわかります。したがって、上記の手順を2つのサブ区間a[0…4]とa[6…9]に対して繰り返すことができます。
```
配列: 48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
 0 1 2 3 4 5 6 7 8 9
```
平均時間計算量: O(N*logN)

コード実装:

公共 静的  voidクイックソート( int a[], int l, int r){
もし(l>=r)
戻る; 
 
 int i = l; int j = r; int key = a[l]; // 最大の数字をキーとして選択  
 
 (i<j) { 
 
 while (i<j && a[j]>=key) //右から左へ、keyより小さい最初の値を検索します 
             j--;
もし(i<j){
             関数 i は、次の式で表されます。
             私は++;
         } 
 
 while (i<j && a[i]<key) //左から右へ、キーより大きい最初の値を検索します 
             私は++; 
 
もし(i<j){
             関数 i は、次の式で表されます。
             j--;
         }
     }
 //i == j  
     a[i] = キー;
     quickSort(a, l, i- 1 ); // 再帰呼び出し 
     quickSort(a, i+ 1 , r); // 再帰呼び出し 
 }

キー値は、中間数や乱数など、さまざまな形式で選択でき、アルゴリズムの複雑さにさまざまな影響を与えます。

6. マージソート

基本的な考え方: 参照マージソートは、マージ操作に基づく効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。
まず、順序付けられた 2 つのシリーズを結合する方法を検討します。これは非常に簡単です。2 つの数列の最初と最後の数字を比較し、小さい方を先に取って、対応する数列の数字を削除するだけです。次に、それらを再度比較します。シーケンスの 1 つが空の場合は、他のシーケンスからデータを 1 つずつ取り出します。
```
 // 順序付けられた配列 a[] と b[] を c[] にマージします 
 voidメモリ配列( int a[], int n, int b[], int m, int c[])
 {
整数i、j、k; 
 
 i = j = k = 0 ;
ただし、 (i < n && j < m)
 {
もし(a[i] < b[j])
         c[k++] = a[i++];
それ以外 
         c[k++] = b[j++];
 } 
 
 (i < n)の場合
     c[k++] = a[i++]; 
 
一方、 (j < m)
     c[k++] = b[j++];
 }
```
順序付けられたシリーズをマージするという上記の問題を解決した後、マージソートを見てみましょう。基本的な考え方は、配列を 2 つのグループ A と B に分割することです。これら 2 つのグループのデータが順序付けられている場合、これら 2 つのデータグループを簡単にソートできます。これら 2 つのグループのデータを順序どおりにするにはどうすればよいでしょうか?
グループAとグループBはそれぞれ2つのグループに分けられます。同様に、分割されたグループにデータが 1 つしかない場合、グループは秩序が確立されたとみなされ、隣接する 2 つのグループを結合できます。このように、系列を再帰的に分解してからマージすることで、マージソートが完了します。
プロセス：
マージソート
平均時間計算量: O(NlogN)
マージソートの効率は比較的高いです。シーケンスの長さが N であるとすると、シーケンスを小さなシーケンスに分割するには logN ステップかかります。各ステップは、順序付けられたシーケンスをマージするプロセスです。時間の複雑さは O(N) として記録できるため、全体の時間の複雑さは O(N*logN) です。

コード実装:

公共 静的  void merge_sort( int a[], int first, int last, int temp[]){ 
 
 (最初 < 最後)の場合{
 int中間 = (最初 + 最後) / 2 ;
      merge_sort(a,first,middle,temp); // 左半分をソートする 
      merge_sort(a,middle+ 1 ,last,temp); //右半分をソートする 
      mergeArray(a,first,middle,last,temp); // 左と右の部分を結合する 
  }
 }

 //マージ: 2つのシーケンス a[first-middle]、a[middle+1-end] をマージします。  
公共 静的  void mergeArray( int a[], int first, int middle, int end, int temp[]){
 int i = 最初;
 int m = 中央;
 int j = 中間 + 1 ;
 int n = 終了;
整数k = 0 ;
 (i<=m && j<=n)の場合{
もし(a[i] <= a[j]){
          temp[k] = a[i];
          関数
          私は++;
      }それ以外{
          temp[k] = a[j];
          関数
          j++;
      }
  }
 (i<=m) {
      temp[k] = a[i];
      関数
      私は++;
  }
 (j<=n) {
      temp[k] = a[j];
      関数
      j++;
  } 
 
 ( int ii = 0 ; ii < k ; ii++ )の場合{
      a[first + ii] = temp[ii];
  }
 }

7. ヒープソート

基本的な考え方:
イラスト: (88,85,83,73,72,60,57,48,42,6)
ヒープソート
平均時間計算量: O(NlogN)
ヒープを毎回復元する際の時間計算量は O(logN) であるため、ヒープ復元操作は合計で N - 1 回行われ、さらにヒープが以前に確立されたときの N / 2 回の下方調整が行われるため、各調整の時間計算量も O(logN) になります。 2 番目の操作にかかる時間の合計は依然として O(N * logN) です。

Java コードの実装:

 //最小ヒープを構築する 
公共 静的  void MakeMinHeap( int a[], int n){
 ( int i=(n- 1 )/ 2 ; i>= 0 ; i--) {
     MinHeapFixdown(a,i,n);
 }
 }
 //ノード i から調整を開始します。n はノードの総数です。0 から数えると、ノード i の子ノードは 2*i+1、2*i+2 です。  
公共 静的  void MinHeapFixdown( int a[], int i, int n){ 
 
 int j = 2 *i+ 1 ; //子ノード 
整数温度 = 0 ; 
 
 (j<n) {
 // 左と右の子ノードのうち最小のものを見つける 
 (j+ 1 <n && a[j+ 1 ]<a[j])の場合{
           j++;
       } 
 
もし(a[i] <= a[j])
壊す; 
 
 //大きいノードを下へ移動 
       temp = a[i];
       関数 i は、次の式で表されます。
       a[j] = 一時; 
 
       私 = j;
       j = 2 * i + 1 ;
   }
 }

公共 静的  void MinHeap_Sort( int a[], int n){
整数温度 = 0 ;
  最小ヒープを作成します(a,n); 
 
 ( int i=n- 1 ;i> 0 ;i--) {
      温度 = a[ 0 ];
      a[ 0 ] = a[i];
      a[i] = 温度;
      MinHeapFixdown(a, 0 ,i);
  }
 }

8. 基数ソート

ビンソート

基本的な考え方:
BinSortの考え方は非常にシンプルです。まず、配列A[MaxValue]を作成します。次に、各数字を対応する位置に配置し（たとえば、添字17の配列位置に17を配置します）、最後に配列を走査してソートされた結果を取得します。
図:
ビンソート
質問：
シーケンス内に大きな値がある場合、BinSort のソート方法では大量のスペースのオーバーヘッドが浪費されます。

基数ソート

基本的な考え方:
基数ソートは BinSort に基づいており、基数を制限することでスペースのオーバーヘッドを削減します。
プロセス：
プロセス1
プロセス2

（１）まず、基数を10に決定し、配列の長さも10にします。各数値34は、これらの10個の数値の中で独自の位置を見つけます。
(2) BinSortでは34という数字を配列のインデックス34に直接配置しますが、基数ソートでは34を3と4に分けます。最初のソートでは最後の桁に基づいてインデックス4に数字を配置し、2回目のソートでは最後から2番目の桁に基づいてインデックス3に数字を配置します。その後、配列を走査します。

Java コードの実装:

公共 静的  void RadixSort( int A[], int temp[], int n, int k, int r, int cnt[]){ 
 
 //A: 元の配列 
 //temp: 一時配列 
 //n: シーケンスの桁数 
 //k: ***2 の桁数 
 //r: 10進数 
 //cnt: bin[i]の数を格納します  
 
 ( int i = 0 、 rtok = 1 ; i < k ; i++ 、rtok = rtok*r) { 
 
 //初期化 
 ( int j = 0 ; j < r ; j++ )の場合{
           cnt[j] = 0 ;
       }
 // 各ボックス内の数字の数を計算する 
 ( int j = 0 ; j < n ; j++ )の場合{
           cnt[(A[j]/rtok)%r]++;
       }
 //cnt[j]の数は最初のj個のボックスの数字の合計数に変更されます 
 ( int j = 1 ; j < r ; j++ )の場合{
           cnt[j] = cnt[j- 1 ] + cnt[j];
       }
 for ( int j = n- 1 ; j>= 0 ; j--){ //理解すべき重要なポイント 
           cnt[(A[j]/rtok)%r]--;
           temp[cnt[(A[j]/rtok)%r]] = A[j];
       }
 ( int j = 0 ; j < n ; j++ )の場合{
           A[j] = temp[j];
       }
   }
 }