上位 10 の古典的なソート アルゴリズムの詳細な説明: バブル ソート、選択ソート、挿入ソート

[[377307]]

1. アルゴリズムの評価基準

ソートアルゴリズムを説明する前に、まずアルゴリズムが一般的にどのような角度から評価されるかを理解しましょう。

アルゴリズムについて少しでも知っている人なら、このことは分かるでしょう。 「これら2つの基準は、時間の複雑さと空間の複雑さです」

• 時間計算量は、実は非常に理解しやすいものです。文字通りの意味から、アルゴリズム全体の実行にどれくらいの時間がかかるか、ということは非常によく理解できます。時間計算量を判断する基準は 2 つあります。実際、厳密に言えば、「最良のケース、平均的なケース、最悪のケース」の 3 つがありますが、一般的には最良のケースについては議論しません。意味がないからです。そのため、一般的には平均的なケースと最悪のケースについて議論します。

そして一般的に、時間計算量は私たちが最も注意を払うものです。結局のところ、私たちの日常生活で気になるのは、ソフトウェアがどれだけ速く実行されるかです。それがとんでもなく遅いと、ユーザーエクスペリエンスは特に悪くなります。通常、私たちは、これがどれだけのメモリスペースを消費するかを尋ねません。

もう 1 つのポイントは、「時間計算量はアルゴリズムの核心である」ということです。結局のところ、少し大きい空間計算量は許容されますが、アルゴリズムの時間計算量を削減できない場合は、スペースを追加しても問題は解決しません。

• 空間複雑度は、実は非常に理解しやすいものです。これは、「アルゴリズムの実行中に占有されるメモリ領域の量」を指します。一般的に、人々は空間複雑度にあまり注意を払っていません。しかし、ここにデータ構造の例があります。この概念をすぐに理解できます。

このデータ構造は HashMap で、時間のためにスペースを犠牲にするデータ構造です。「Map は、キーが必要な要素を直接取得できます。」

HashMap が非常に強力であることがわかれば、大企業がデータ構造のソース コードを尋ねるときに HashMap のソース コードについて尋ねることが多い理由がわかります。その理由は、その設計が非常に悪いためです。

2. ソートアルゴリズムの分類

上記のアルゴリズムの評価基準を理解した後、これらのソートアルゴリズムがどのように分類されるかを確認する必要があります。分類方法は主に 2 つあります。

並べ替えの種類

ここに画像の説明を挿入

ここでの比較は、誰もが通常理解している比較と同じであり、つまり、ソートは主に比較によって行われます。

• 安定していますか？

ここでの安定性については簡単に説明する必要があります。ここでの安定性とは、ソート後の同じ要素の相対的な位置がソート前と同じかどうかを指します。変化がない場合、アルゴリズムは安定していると呼ばれます。これは理解しにくいかもしれません。ここでは、次の図を使用して、印象を深めるのに役立ちます。

上記の概念を理解すると、ソートアルゴリズムを説明するときに提案されるいくつかの概念をよりよく理解できるようになります。

3. 古典的なソートアルゴリズムのトップ 10 - バブル ソート、選択ソート、挿入ソート

3.1-バブルソート

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

泡といえば、まず頭に浮かぶのは、金魚が泡を吹いている下の写真でしょう。

[[377308]]

図を見ると、上に行くほどバブルが大きくなっていることがわかります。これがバブルソートの核となる考え方です。各サイクルで、残りのソートされたシーケンスの最大値または最小値を見つけ、それをシーケンスの最後または先頭に置き換えます。理解するために、次の簡単な例を見てみましょう。

これがバブルソートの基本的な考え方です。バブルソートの特徴を簡単にまとめると次のようになります。

• 各ソートは「少なくとも1つの要素の最終的な位置を決定」できる
• バブルソートは「安定」しており、「要素のサイズが異なる場合にのみ要素の位置が交換される」ため、ソートの前後で同じ要素の相対的な位置は変化しないため、バブルソートは安定しています。
• バブルソートには「極端なケース」があります。「指定した順序は大きいものから小さいもの」であるが、「元のシーケンスの順序は小さいものから大きいもの」である場合、「2 つの要素を比較するたびに、その 2 つの要素を交換する必要がある」ことがわかります。これがバブルソートの最も極端なケースです。

アルゴリズム図:

ここに画像の説明を挿入

コード例:

公共 静的void main(String[] args) {
 int []数値 ={7,4,9,3,2,1,8,6,5,10};
 長い開始時間 = System.currentTimeMillis();
 ( int i=0;i<num.length-1;i++)の場合{
 ( int j=0;j<num.length-1-i;j++)の場合{
   num[j]>num[j+1]の場合
整数  temp =num[j+1];
    num[j+1] = num[j];
    num[j] =一時;
   }
  }
  System.out.print ( "the" +(i+1)+ " のソート結果:" );
 ( int j=0;j<num.length;j++)の場合
   システム.out.print (num[j]+ " " );
  System.out.println( ) ;
 }
 長い endTime=System.currentTimeMillis();
 System.out.println ( "プログラム実行時間:" +(endTime-startTime)+ "ms" );
 }

ここに画像の説明を挿入

複雑性分析:

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

• 時間計算量時間計算量は2つの側面から判断する
  • 平均すると、このアルゴリズムの複雑さは主に要素を比較するプロセスにあります。つまり、if (num[j]>num[j+1]) のプロセスです。このプロセスは、2 層の for ループの平均回数です。計算すると n*(n-1)/2 になります。最大数まで行くと、時間の複雑さは O(n*n) であることがわかります。
  • 最悪のケースは、上で述べた極端なケースです。ただし、極端なケースでは、平均的なケースよりも要素の交換操作が 1 つ多く実行されますが、比較の数は変わらないため、時間計算量も O(n*n) になります。
• 空間の複雑さ

また、ソート処理全体を通じてスペースが追加されていることもわかります。このスペースは、定義した temp であり、主に要素の交換に役立ちます。したがって、バブル ソートのスペース計算量は O(1) です。

3.2- 選択ソート

アルゴリズムの考え方: 選択ソートの鍵は選択です。選択の方法は、各サイクルで最小の要素を選択し、最小の要素をソートされたシーケンスの先頭の要素に置き換えることです。いつものように、次の図は、この選択プロセスをよりよく理解するのに役立ちます。

これは、基本的に理解できる選択ソートの基本概念です。上記のバブルソートと区別する必要があるのは、選択ソートは「比較が完了した後に2つの要素の位置を直接交換するのではなく、現在のシーケンスの最小の要素のみを記録する」ということです。最小の要素を見つけた後、最小の要素はキューの先頭の要素に置き換えられます。これを理解した後、選択ソートの特性について説明しましょう。

• 「各ループは要素の最終位置を決定できなければならない」これはバブルソートと同じである
• 選択ソートも不安定です。これはわからないかもしれません。いつものように、次の図で説明して理解できるようにします。

アルゴリズム図:

ここに画像の説明を挿入

コード例:

公共 静的void main(String[] args) {
 int []数値 ={7,4,9,3,2,1,8,6,5,10};
  長い開始時間 = System.currentTimeMillis();
 ( int i=0;i<num.length-1;i++)の場合{
整数 最小値= i;
 ( int j=i+1;j<num.length;j++)の場合{
    if(num[ min ]>num[j]) {
最小値= j;
    }
   }
   if(i!= min ) {
整数  temp =数値[i];
    num[i]=num[分];
    num[分]=温度;
   }
   System.out.print ( "the" +(i+1)+ " のソート結果:" );
 ( int j=0;j<num.length;j++)の場合
    システム.out.print (num[j]+ " " );
   System.out.println( ) ;
  }
  長い endTime=System.currentTimeMillis();
  System.out.println ( "プログラム実行時間:" +(endTime-startTime)+ "ms" );
 }

複雑性分析:

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

• 時間計算量時間計算量は2つの側面から判断する
  • 平均すると、このアルゴリズムの複雑さは主に要素を比較するプロセスにあります。つまり、if (num[min]>num[j]) のプロセスです。このプロセスは、2 層の for ループの平均回数です。計算すると n*(n-1)/2 になります。最大数まで行くと、時間の複雑さは O(n*n) であることがわかります。
  • 最悪のケースは、平均ケースと本質的に同じです。平均ケースでも最悪のケースでも、最小要素と先頭要素の位置は最後にのみ置き換えられ、比較回数は同じであるため、時間計算量も O(n*n) です。
• 空間の複雑さ

また、ソート処理全体を通じて 2 つのスペースが追加されることもわかります。このスペースは定義した temp と min なので、選択ソートのスペース複雑度も一定レベル、つまり O(1) になります。

3.3- 挿入ソート

アルゴリズムのアイデア：挿入ソートのアルゴリズムのアイデアは、シーケンス全体を 2 つのセグメントに分割することです。1 つのセグメントはソートされたシーケンスであり、もう 1 つのセグメントはまだ必要がない状態です。たとえば、次の図に示すように:

挿入シーケンスは、2つのシーケンスに分割された後、ソートするシーケンスの先頭要素を選択し、順序付けられたシーケンスの末尾から始めて、その都度順序付けられたシーケンスに挿入します。要素よりも大きい場合は、要素を後ろにずらします。要素よりも小さい要素が現れると、現在の位置に挿入します。これが挿入ソートの名前の由来です。

長々と説明してもまだよく理解できないかもしれませんので、次の図でアルゴリズムの実行プロセスを詳しく説明しましょう。

挿入ソートアルゴリズムの基本的な考え方を理解した後、アルゴリズムの特徴を見てみましょう。

• これは実際には機能ではありません。上記の 2 つのアルゴリズムと比較すると、このアルゴリズムは上記のバブル ソートや選択ソートとは異なることがわかります。各ループで要素の最終的な位置を決定できます。「挿入ソートでは、各ループ後の要素の最終的な位置を一意に決定することはできません。各ループ後の一部の要素の相対的な位置のみを決定できます。」
• 挿入ソートもバブルソートと同様に「極端なソート状況」がありますが、バブルソートの極端な状況は最悪の状況であり、挿入ソートの極端な状況は最良の状況です。つまり、シーケンスが基本的に順序付けられている場合、挿入ソートは最も速く、時間計算量はO(n)、つまり線形レベルに達することができます。「シーケンスが順序付けられると、forループは引き続き実行する必要がありますが、whileループではまったく実行する必要がないため」、これが挿入ソートの線形レベルの鍵です。バブルソートと選択ソートと比較すると、「どちらも2層のforループを介して実行されますが、挿入ソートループの2層目はwhileを介して実行され、対応する終了条件があります」ため、挿入ソートのパフォーマンスは上記の2つよりも比較的優れています。もちろん、「この状況はシーケンスが基本的に順序付けられている場合にのみ存在します。」

アルゴリズム図:

ここに画像の説明を挿入

コード例:

公共 静的void main(String[] args) {
 int []数値 ={7,4,9,3,2,1,8,6,5,10};
  長い開始時間 = System.currentTimeMillis();
 ( int i=1;i<num.length;i++)の場合{
整数  temp =数値[i];
整数j = i;
   while(j>0&& temp <num[j-1]) {
    num[j] = num[j-1];
    j --;  
   }
   もし(j!=i) {
    num[j] =一時;
   }
   System.out.print ( "" +i+ "番目のソート結果:" );
 ( int k=0;k<num.length;k++)の場合
    システム.out.print (num[k]+ "" );
   System.out.println( ) ;
  }
  長い endTime=System.currentTimeMillis();
  System.out.println ( "プログラム実行時間:" +(endTime-startTime)+ "ms" );
 }

ここに画像の説明を挿入

複雑性分析:

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

• 時間の複雑さ 時間の複雑さは 3 つの側面から判断します。ここでは、上で述べた極端なケースについて触れる必要があります。
  • 最良の場合の時間計算量は線形レベルO(n)に達する可能性がある。
  • 平均すると、私たちのアルゴリズムの複雑さは主に要素を比較するプロセスにあります。
  • 最悪のケースは、平均ケースと本質的に同じです。平均ケースでも最悪のケースでも、比較の数は同じなので、時間の計算量も O(n*n) です。
• 空間の複雑さ

また、ソート処理全体を通じて 2 つのスペースが追加されることもわかります。このスペースは定義した temp と j なので、選択ソートのスペース計算量も一定レベル、つまり O(1) になります。

この記事はWeChat公式アカウント「萌萌哒铤铤」から転載したもので、以下のQRコードからフォローできます。この記事の転載については、Mengmengda Rangrangの公式アカウントまでご連絡ください。