上位 10 の古典的なソート アルゴリズムの詳細な説明: シェル ソート、マージ ソート、クイック ソート

[[378304]]

上位 10 の古典的なソート アルゴリズム - シェル ソート、マージ ソート、クイック ソート 序文 これは、上位 10 の古典的なソート アルゴリズムの詳細な説明の 2 番目の記事です。 これは、最初の記事へのリンクです: 上位 10 の古典的なソート アルゴリズムの詳細な説明 (I) バブル ソート、選択ソート、挿入ソート。 まだ読んでいない友人は、見てみてください。

毎回説明するときは、まずテキストを使用してアルゴリズムの基本的な考え方を理解していただきます。次に、画像を使用してソート アルゴリズムの動的な実行プロセスを分析し、アルゴリズムをよりよく理解していただきます。

毎回絵を描くのはとても面倒で時間がかかります。ですから、この記事がうまく書かれている、あるいは役に立つと思ったら、トリプルクリックするか、私の公開アカウント「萌萌哒的擤擤」をフォローしてください。これは私にとって本当に重要です。皆さん、ありがとうございます。

さっそく本文を始めましょう！

1- シェルソート

アルゴリズムのアイデア:

実際、シェル ソートの考え方は非常に単純です。シェル ソートの基本的な考え方は、最初の記事で説明した挿入ソートの基本的な考え方と同じですが、「シェル ソートには、挿入ソートに比べてステップが 1 つ多くあります。それは、ステップ長を決定することです。」 以前の挿入ソート プロセスでは、ステップ長は 1 に固定されていましたが、シェル ソートではステップ長は固定されておらず、「配列の長さの半分から始まり、ステップ長が 1 に達するまで、各グループのソート後にステップ長が半分になります。」 この時点で、ソートが完了します。

そうは言っても、シェルソートをよりよく理解できるように図を使用しましょう。

上の図を読んだ後、誰もがヒルソートアルゴリズムの考え方を基本的に理解したと思いますので、ヒルソートアルゴリズムの特徴を分析してみましょう。

• Shell ソート アルゴリズムは不安定です。ここで、このような疑問が生じるかもしれません。Shell ソート アルゴリズムの本質は挿入ソートですが、ステップの長さを決定するための追加のステップがあります。挿入ソートは安定しているのに、Shell ソートは不安定なのはなぜでしょうか。実は、鍵となるのはグループ化後です。グループ内の挿入ソートが間違いなく安定していることは誰もが知っています。鍵となるのは、Shell ソート プロセスで複数のグループ化が行われることです。すると、前のグループ化では安定しますが、次のグループ化では不安定になります。

あまり多くを語るよりも、直接例を挙げた方が理解しやすいでしょう。

• シェルソートは、時間計算量が O(N*N) を突破した「最初の」アルゴリズムであり、非常に意義深いものです。時間計算量はわずか O(N*log N) です。

アルゴリズム図:

ここに画像の説明を挿入

コード例:

「アルゴリズムの考え方に従って変更されないバージョン」：

公共 静的void main(String[] args) {
 int []数値 ={7,4,9,3,2,1,8,6,5,10};
  長い開始時間 = System.currentTimeMillis();
  //ステップの長さを指定する
( intステップ = 数値の長さ / 2; ステップ > 0; ステップ / = 2) {
   System.out.println ( "ステップサイズ" +step+ "でのグループソート:" );
   //ステップサイズが決定したら、グループをバッチで挿入してソートする必要があります
( int l=0;l<step;l++)の場合{
    // 挿入ソートコード
( int i=l+step;i<num.length;i+=step)の場合{
整数  temp =数値[i];
整数j = i;
     while(j>0&& temp <num[j-step]) {
      num[j]=num[jステップ];
      j-=ステップ;
      //ここで注意すべきことは、jステップが境界を越える可能性があるため、引き続き判断する必要があることです。
      // 以前の挿入ソートでは、ステップサイズは常に 1 だったので、while ループでブロックしていましたが、ステップサイズは変更されます。
      //したがって、ここで事前に判断する必要があります。そうしないと、Jinhui は範囲外の配列を持つことになります。
      if(jステップ<0)
       壊す;
     }
     もし(j!=i) {
      num[j] =一時;
     }
    }
    System.out.println ( "" +l+ "グループ化ソート:" );
 ( int k=0;k<num.length;k++)の場合
     システム.out.print (num[k]+ "" );
    System.out.println( ) ;
   }
   System.out.println( ) ;
  }
  長い endTime=System.currentTimeMillis();
  System.out.println ( "プログラム実行時間:" +(endTime-startTime)+ "ms" );
 }

しかし、ヒルソートの考え方に本当に従うと、3層のforループでは明らかに時間の計算量がこれまで経験した最悪のケース、つまりO(N*N*N)に達することがわかります。そのため、主にグループ化ソートプロセスを改善するための改善が必要です。以前は、ステップサイズを決定した後、forループを使用して循環グループをソートしていました。ここでは、次のforループと一緒に循環グループ化を直接実行するように変更します。

改善されたコード:

公共 静的void main(String[] args) {
 int []数値 ={7,4,9,3,2,1,8,6,5,10};
  長い開始時間 = System.currentTimeMillis();
 ( intステップ = 数値の長さ / 2; ステップ > 0; ステップ / = 2) {
   System.out.println ( "ステップサイズ" +step+ "でのグループソート:" );
   System.out.println ( "ループグループのソート:" );
 ( int j = ステップ; j < 数値の長さ; j++) {
整数  temp =数値[j];
整数k=j;
    while(kステップ>=0&& temp <num[kステップ]) {
     num[k]=num[kステップ];
     k-=ステップ;
    }
    num[k] =温度;
 ( int l=0;l<num.length;l++)の場合
     システム.out.print (num[l]+ " " );
    System.out.println( ) ;
   }
  }
  長い endTime=System.currentTimeMillis();
  System.out.println ( "プログラム実行時間:" +(endTime-startTime)+ "ms" );
 }

改良されたアルゴリズムは2層のforループを使用するため、時間の計算量はO(N*log N)に達する。

計算量分析: ヒルソートの基本的な考え方を理解した後、その時間計算量と空間計算量を分析する必要があります。

• 時間計算量

それぞれのケースにおけるシェルソートの時間計算量は、主に要素の数とグループ化の数に依存します。グループ化の数はちょうどlog Nであることがわかったので、シェルソートの時間計算量はO(N*log N)だけであることがわかります。

• 空間の複雑さ

ソート処理全体を通じてキーの保存場所を 1 つだけ追加するだけなので、シェル ソートの空間計算量は O(1) という一定レベルであることがわかります。

2-マージソート

アルゴリズムの考え方：マージソートの考え方の本質は分割することです。シーケンス全体を複数のシーケンスに分割し、各シーケンスを最初にソートします。これは「分割の考え方で分割する」という考え方であり、「マージソートで戻す」という考え方でもあります。

次に、すべてのシーケンスを統合します。これは「ソート内のマージ」であり、「ソート内のマージ」でもあります。アイデアはこれで終わりですが、問題を解決することはできません。理解を助けるために、次の図を使用しましょう。

図を見ると、上記の分割プロセスとマージプロセスは再帰と非常に似ていることがわかります。これらはすべて、特定の終了条件に従って実行されます。つまり、これはマージソートが「再帰」という考え方を通じて記述できることを示唆しています。

これでマージソートの基本的な考え方はほぼ理解できました。次に、マージソートの特徴を見てみましょう。

上記のデモからわかるように、マージソートは安定しています。

マージソートは大量のメモリ空間を消費します。このメモリ空間はバブルソートなどのソートアルゴリズムと比較されます。バブルソートのメモリ空間は一定レベルでしか存在しないのに対し、マージソートは線形メモリ空間を消費するため、「大量」という形容詞が使われます。消費されるメモリ空間はソートするシーケンスの長さに相当します。つまり、O(n) の複雑さです。

アルゴリズム図:

ここに画像の説明を挿入

コード例:

読者が理解しやすいように、重要なコードにコメントを追加しました。

公共 静的  int []ソート( int []num) {
        //分割後の配列に要素が1つしかない場合、
        // すると、マージ処理を開始できることになるので、直接戻ります。
  数値の長さ<2の場合
数値を返します。
 int中間 = 数値の長さ / 2;
  //左と右のシーケンスをインターセプトする
int []左=Arrays.copyOfRange(num, 0, middle);
 int [] right =Arrays.copyOfRange(num, middle, num.length);
 merge(sort( left ), sort( right ))を返します。
 }
公共 静的  int [] マージ ( int []左、 int []右) {
 int []num = 新しいint [左.length +右.length];
整数i=0,j=0,k=0;
  //終了条件は&&であり、そのうちの1つが満たされない限り、ループは終了することに注意してください。
  while(i<左辺の長さ&&j<右辺の長さ) {
   if(左[i] <右[j] )
    num[k++] =左[i++];
それ以外  
    num[k++] =右[j++];
  }
  //上記のループを抜けると、値を持つシーケンスは1つだけであることを意味します
  //各シーケンスを再度チェックする必要があり、次の2つのループは相互に排他的であるため、そのうちの1つだけが実行されます。
  //またはどちらも実行しない
  while(i<左 .長さ) {
   num[k++] =左[i++];
  }
  while(j<右.長さ) {
   num[k++] =右[j++];
  }
 ( int l=0;l<num.length;l++)の場合
   システム.out.print (num[l]+ "" );
  System.out.println( ) ;
数値を返します。
 }
公共 静的void main(String[] args) {
 int []数値 ={7,4,9,3,2,1,8,6,5,10};
  長い開始時間 = System.currentTimeMillis();
  num=ソート(num);
 // ( int i=0;i<num.length;i++)の場合{
 // システム.out.print (num[i]+ "" );
 // }
 // System.out.println () ;
  長い endTime=System.currentTimeMillis();
  System.out.println ( "プログラム実行時間:" +(endTime-startTime)+ "ms" );
 }

ここではすべての要素を説明するつもりはありません。区間の左半分の要素を並べ替えるプロセスだけを説明します。右半分は想像力を働かせて考えてください。これは難しくないはずです。

これで、シーケンスの長さが 2 の累乗でない場合、シーケンスのその後の分割によって上記と同様の状況が発生することが誰もが理解できるはずです。結局のところ、区間を分割するプロセス全体は、「区間の中心をバイナリ ツリーに分割する」ことに似ています。

複雑性分析:

マージソートの基本的な考え方を理解した後、その時間計算量と空間計算量を分析する必要があります。

• 時間計算量

実際、上記のアルゴリズムから、for ループを使用せず、再帰を通じてループ問題を解決していることがはっきりとわかります。したがって、より効率的です。上記のデモンストレーション プロセスで書いたように、この実行のレイヤー数は 2 * log N で、各レイヤーで操作される要素は N であるため、時間計算量は 2 * N * log N ですが、定数は無視できるため、時間計算量は O(N*log N) に抑えられます。以前のアルゴリズムの時間計算量 O(N*N) と比較すると、「時間計算量が大幅に削減されている」ことがわかります。また、この時間計算量は「平均的なケースだけでなく、最悪のケースにも適用できます」。

• 空間の複雑さ

また、ソート処理全体では、2 次ソート後のシーケンスを保存するために、ソートされたシーケンスの長さに等しいスペースを追加する必要があることがわかります。そのため、必要なスペースの複雑さは線形レベル O(n) です。以前のソート アルゴリズムと比較すると、この複雑さは確かに少し大きくなります。ただし、全体的な時間複雑さが大幅に削減されていることも明らかです。これは、明らかに時間と引き換えにスペースを犠牲にする方法です。最初の記事で説明した HashMap と比較してください。

3- クイックソート

アルゴリズムのアイデア:

クイックソートのアルゴリズムの考え方も理解しやすいです。しかし、言葉で説明すると少し難しいかもしれませんので、できるだけ簡単に説明します。それでも理解できなくても大丈夫です。絵を使ったデモンストレーションで理解を深めていきます。

クイックソートの考え方は、ソートするたびに「参照値を選択する」ことです。この参照値を選択した後、さらに 2 つの「ポインタ」が必要になります。このポインタは C++ のポインタではありませんが、機能は似ています。主に位置をマークするのに役立ちます。「これら 2 つのポインタは、ソートするシーケンスの先頭要素と末尾要素をそれぞれ指します。」

まず、「末尾の要素から始めて、右から左に参照値より大きくない最初の要素を検索します」。それを見つけたら、まず、以前に末尾の要素を指していたポインタを要素の位置にポイントし、次に参照値を先ほど見つけた要素と交換します。

このステップの後は、「先頭要素から始めて、左から右に参照値より小さくない最初の要素を検索する」必要があります。要素を見つけた後も、上記の手順に従います。まず、以前に先頭要素を指していたポインターを要素に向け、次に参照値を要素と交換します。

上記の手順を、「ヘッド ポインターとテール ポインターが出会うまで繰り返します。出会うと、最初のソートが完了したことを意味します」。最初のソートが完了した後、シーケンスが「ベンチマーク値の左側にあるすべての要素がベンチマーク値以下であり、ベンチマーク値の右側にあるすべての要素がベンチマーク値以上である」状態であることがわかります。

後続のソートでは、ベンチマーク値の左側と右側のシーケンスに対して上記の操作を実行するだけです。

さて、アルゴリズムのテキスト説明は完了しました。もちろん、この時点で多くの友人は間違いなく「何を言っているの？」と思うでしょう。それは問題ではありません。いつものように、写真を使用して話しましょう。

ここでは最初のソート処理のみを説明しますが、その後のソート処理は自分で理解できると思います。クイックソートの基本的なアルゴリズムの考え方を理解した後、クイックソートの特徴について少し説明する必要があります。

クイックソート自体は不安定です。まずは不安定なクイックソートがどのようなものかを理解しましょう。

上の図から、クイックソートが不安定な理由がわかります。

「クイック ソートにも極端なケースがあります」。つまり、クイック ソートが「すでに順序付けられたシーケンス」をソートする場合、時間の計算量は O(n*n) に急上昇し、これが最悪の時間の計算量となります。この状況は、実際に自分でシミュレーションすることで知ることができます。ここではあまり詳しく説明しません。アルゴリズム図:

ここに画像の説明を挿入

コード例:

読者が理解しやすいように、重要なコードにコメントを追加しました。

公共 静的voidソート( int []num, int  左、 int  右） {
  if(左<右) {
整数 キー=num[左];
 int i =左;
 int j =右;
   //この部分はアルゴリズムの核となる考え方です
   i<j の場合
    // 右から左へ、参照値より大きくない最初の要素を検索します
    while(i<j&&num[j]>=キー) {
     j --;  
    }
    i<jの場合{
     num[i] = num[j];
    }
    // 左から右へ、参照値より小さくない最初の要素を検索します
    i<j&&num[i]<=キーの場合
     私は++;
    }
    i<jの場合{
     num[j] = num[i];
    }
   }
   num[i]=キー;
 ( int k=0;k<num.length;k++)の場合{
    システム.out.print (num[k]+ "" );
   }
   System.out.println( ) ;
   //残りのシーケンスを再帰的にソートし続ける
   ソート(num, left , i-1);
   ソート(num, i+1,右);
  }
 }
公共 静的void main(String[] args) {
 int []数値 ={7,4,9,3,2,1,8,6,5,10};
  長い開始時間 = System.currentTimeMillis();
  ソート(数値、0、数値の長さ-1);
  長い endTime=System.currentTimeMillis();
  System.out.println ( "プログラム実行時間:" +(endTime-startTime)+ "ms" );
 }

上記の動的デモンストレーション図は非常にわかりやすく示されているため、デモンストレーションは描きません。

複雑性分析:

クイックソートの基本的な考え方を理解した後、その時間計算量と空間計算量を分析する必要があります。

• 時間計算量

実際、上記のアルゴリズムから、 for ループを使用せず、再帰によってループ問題を解決したことがはっきりとわかります。したがって、より効率的です。

上で示したように、平均時間計算量は O(N * log N) ですが、前述したように、クイック ソートには「すでに順序付けられたシーケンスのクイック ソート」という極端なケースがあり、これはバブル ソートに似ており、時間計算量は O(N * N) です。これは注意を払う必要があることですが、ほとんどの場合、クイック ソートは依然として最も効率的なソート アルゴリズムです。

• 空間の複雑さ

また、ソートプロセス全体では、各ソートサイクルでキーを格納するためのスペースを追加する必要があることがわかります。クイックソートは実際には上記のマージソートに似ており、バイナリツリーを使用する概念にも似ているため、そのスペース計算量はO(log N)です。

上位 10 の古典的なソートアルゴリズムの詳細な説明の第 2 号が終了しました。UP の記事がうまく書かれている、または役立つと思われる場合は、UP の公式アカウントをフォローできます。新参の UP はあなたのサポートを必要としています!!!