Go 言語アルゴリズムの美しさ - 基本的なソート

[[404642]]

この記事はWeChatの公開アカウント「roseduanの執筆場所」から転載したもので、著者はroseduanです。この記事を転載する場合は、roseduanが執筆しているローカルの公開アカウントまでご連絡ください。

Rosedb ビデオを録画するときに、穴を掘って、一般的なデータ構造とアルゴリズムを Go 言語で実装すると言いました。すでにそのような記事はたくさんありますが、Rose 兄弟?? 埋めなければならない穴があります! 勇気を出してこのシリーズを書くしかないので、これを Go 言語アルゴリズムの美しさと呼びましょう!

ソートは非常に古い問題であり、コンピュータ分野における古典的なアルゴリズム問題の 1 つです。次の記事では、一般的なソート アルゴリズムについて説明します。

完全なコードを添付し、関連する Leetcode の質問をいくつかお勧めします。これらの質問は、アルゴリズムの知識を学習して強化するだけでなく、面接でより快適に過ごすのにも役立ちます。

この記事では、バブルソート、選択ソート、挿入ソートという 3 つの基本的なソートアルゴリズムを紹介します。

バブルソート

バブルソートは比較と交換に基づいています。基本的な考え方は、データを走査することです。隣接する要素のサイズが異なる場合、それらの位置が交換され、データが完全に順序付けられるまでこのサイクルが繰り返されます。

下の図に示すように、テストデータ -2 45 0 11 -9 があります。

最初のトラバースでは、データ内の最大値 45 が末尾に移動され、次に 45 以外のデータが再度トラバースされて最大値が 45 の前に移動します。最後の要素を走査した後、データは順序どおりになります。

次の図は、バブルソートのプロセスをより直感的に示しています。

コードは次のとおりです。

関数 bubbleSort(data[] int ) {
 i := 0; i < len(データ); i++ {
 j := 0; j < len(data)-i-1; j++ {
         データ[j] > データ[j+1]の場合{
            データ[j]、データ[j+1] = データ[j+1]、データ[j]
         }
      }
   }
 }

ここで、小さな最適化ポイントがあります。データが元々 1 3 4 5 6 のように順序付けられている場合、一度走査した後、交換するデータがないことがわかります。早期に終了して、走査を続ける必要はありません。コードは次のように最適化できます。

関数 bubbleSort(data[] int ) {
   スワップ:= true  
 i := 0; i < len(data) && swap; i++ {
      スワップ =偽 
 j := 0; j < len(data)-i-1; j++ {
         データ[j] > データ[j+1]の場合{
            データ[j]、データ[j+1] = データ[j+1]、データ[j]
            スワップ =真 
         }
      }
   }
 }

バブルソート関連の複雑さ:

選択ソート

選択ソートも理解しやすいです。順序付けられていない配列の場合、配列内の最小値を毎回検索し、それを最初の要素と交換します。

下の図に示すように、テストデータは 20 12 10 15 2 です。最初のトラバーサルで見つかった最小値は 2 です。

そして、それを配列の最初の要素と交換します。

次に、残りのデータで最小値を探し続け、それを配列の 2 番目の要素と交換し、最後のデータまでこのサイクルを繰り返して、配列全体を順序付けます。

次のアニメーションは、選択ソートのプロセス全体を理解するのに役立ちます。

コード実装:

関数selectionSort(data[] int ) {
 i := 0; i < len(data)-1; i++ {
最小:= i
 j : = i + 1; j < len(データ); j++ {
         データ[j] < データ[ min ]の場合
最小= j
         }
      }
      データ[i]、データ[分] = データ[分]、データ[i]
   }
 }

選択ソート関連の複雑さ:

挿入ソート

カードゲームをしていた頃を思い出してください。私たちはどのようにして手札のカードを並べたでしょうか。新しいカードが来たら、すでに手札にあるカードの中から適切な位置を見つけて、それを差し込みます。

挿入ソートでも同じことが言えます。挿入ソートでは、配列内の各データを順に走査し、適切な位置に挿入します。次のアニメーション画像は、このプロセスをより鮮明に示しています。

コードは次のように実装されます。

関数挿入ソート(データ[] int ) {
 i := 0; i < len(data)-1; i++ {
      j, k := i+1、データ[i+1]
に対して; j > 0 && data[j-1] > k; j -- {  
         データ[j] = データ[j-1]
      }
      データ[j] = k
   }
 }

挿入ソート関連の複雑さ:

注: 完全なコードを Github アドレスに置きました:

https://github.com/roseduan/Go-アルゴリズム