データ構造の8つの一般的なソートアルゴリズム

序文

8 つのソートアルゴリズムと 3 つの検索アルゴリズムは、データ構造における非常に基本的な知識ポイントです。ここでは、復習のために 8 つの一般的なソートアルゴリズムをまとめます。

8 つの一般的なソートアルゴリズムには、次の関係があります。

パフォーマンスの比較:

次に、Python を使用してそれぞれを実装します。

直接挿入ソート

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

直接挿入ソートの基本的な考え方は、配列内のすべての要素を、以前にソートされた要素と順番に比較することです。選択された要素がソートされた要素よりも小さい場合は、すべての要素が比較されるまで、その要素が交換されます。

したがって、上記の説明から、直接挿入ソートは 2 つのループで完了できることがわかります。

*** レイヤーループ: 比較するすべての配列要素を走査します

2 番目のループ: このラウンドで選択された要素 (selected) とソートされた要素 (ordered) を比較します。選択済み > 順序付きの場合、2つを入れ替える

コードの実装

シェルソート

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

ヒルソートのアルゴリズムの考え方は、ソートする配列をステップサイズのギャップに応じてグループ化し、各グループの要素を直接挿入ソート法を使用してソートし、ギャップを毎回半分に減らし、上記の操作を繰り返します。ギャップ= 1 の場合、直接挿入を使用してソートを完了します。

同様に、上記の説明から、シェルソートの全体的な実装は 3 つのループで完了する必要があることがわかります。

*** レイヤーループ: ギャップを順番に半分にし、ギャップ = 1 になるまでシーケンスをグループ化します。

2 番目と 3 番目のループは、直接挿入ソートに必要な 2 つのループです。詳細な説明については上記を参照してください。

コード実装:

単純な選択ソート

アルゴリズムのアイデア

単純選択ソートの基本的な考え方：比較 + 交換。

ソートするシーケンスから最小のキーワードを持つ要素を検索します。

最小の要素がソートするシーケンスの最初の要素でない場合は、最初の要素と交換します。

残りのN-1個の要素からキーワードが最も小さい要素を探し、ソートが完了するまで手順(1)と(2)を繰り返す。

したがって、単純な選択ソートも 2 層のループを通じて実装されていることがわかります。

*** レイヤーループ: シーケンス内の各要素を順番に走査します

2 番目のループ: トラバーサルによって取得された現在の要素を残りの要素と順番に比較し、最小要素の条件を満たす場合はそれらを交換します。

コードの実装

ヒープソート

ヒープの概念

ヒープ: 本質的には配列オブジェクトです。特に重要な特性: 任意のリーフノードは、そのすべての親ノードよりも小さい (または大きい) です。この点では、最大ヒープと最小ヒープに分けられます。最大ヒープでは、ノードの要素がその子よりも大きくなければならないことが要求され、最小ヒープでは、ノードの要素がその左と右の子よりも小さくなければならないことが要求されます。どちらも、左と右の子のサイズ関係については何も要求しません。

ヒープソートの使用は、最大ヒープまたは最小ヒープに基づくソート方法です。次に、最大ヒープを通じて実装します。

基本的な考え方:

ヒープソートは以下の手順で実行できます。

まず、シーケンス構造はビッグトップヒープと呼ばれます。

(これは最大ヒープの特性を満たします。ルートノードの要素は現在のシーケンスの最高値である必要があります)

現在の最大ヒープのルートノードを取り出し、シーケンスの末尾の要素と交換します。

(この時点では、シーケンスの末尾の要素はソートされた最高値です。要素が入れ替わるため、現在ルートノードにあるヒープは必ずしも最大ヒープのプロパティを満たすわけではありません)

交換後に n-1 個のシーケンス要素を最大ヒープのプロパティを満たすように調整します。

ヒープ内の要素が 1 つだけになるまで手順 2.3 を繰り返します。

コード実装:

バブルソート

基本的な考え方

バブルソートの考え方は比較的シンプルです。

シーケンスの左側の要素と右側の要素を順番に比較して、右側の要素が常に左側の要素よりも大きいことを確認します。

(最初のラウンドの後、シーケンスの最初の要素は現在のシーケンスの最初の値である必要があります。)

シーケンス内の残りの n-1 個の要素に対して手順 1 を繰り返します。

長さnのシーケンスの場合、合計n-1回の比較を実行する必要がある。

(whileループを使用すると実行回数を減らすことができます)

*コード実装

クイックソート

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

クイックソートの基本的な考え方：穴を掘って数字を埋める+分割統治法

シーケンスからピボットを選択

ここでは、シーケンス内の最大の数字をベンチマーク番号として選択します。

シーケンス内のすべての数字を順番にトラバースします。基本数より大きい数字は右側にあり、基本数より小さい数字は左側にあります。

すべてのサブセットに要素が 1 つだけ含まれるまで、手順 1.2 を繰り返します。

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

1.i = L; j = R; 基数を掘り出して最初のピットa[i]を形成します。

2.j – 後ろから前に向かって小さい数字を探し、見つけたらその数字を掘り出して前の穴a[i]に埋めます。

3. i++ は前方から後方に向かって、それより大きい数を探します。数を見つけると、それを掘り出して、前のピット a[j] に埋めます。

4. i==jになるまで手順2と3を繰り返し、基数をa[i]に代入します。

コード実装:

マージソート

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

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の典型的な応用です。その基本的な操作は、既存のサブシーケンスをマージして完全に順序付けられたシーケンスを実現することです。つまり、最初に各サブシーケンスを順序付けし、次にサブシーケンスのセグメントを順序付けします。

マージソートは実際には次の 2 つのことを行います。

分解 - シーケンスを毎回半分に分割します

マージ - 分割されたシーケンスセグメントをペアで並べ替えてマージします

したがって、マージソートは実際には分割+マージの2つの操作である。

マージする方法は?

L[first…mid] は最初のセグメント、L[mid+1…last] は 2 番目のセグメントで、両端はすでに整列しています。ここで、両端を組み合わせて L[first…last] に到達し、整列させる必要があります。

まず、最初のセグメントと2番目のセグメントから順番に要素を取り出して比較し、小さい方の要素をtemp[]に割り当てます。

前の手順を繰り返します。特定のセグメントが割り当てられたら、別のセグメントの残りの要素をtemp[]に割り当てます。

このとき、temp[]内の要素をL[]にコピーし、得られたL[first...last]を順序付けます。

どのように分解しますか?

ここでは、再帰的な方法を使用して、ソートするシーケンスを最初に 2 つのグループ A と B に分割し、次にシーケンス A と B をソートするプロセスを繰り返します。

グループ化。グループ化後にグループ内の要素が 1 つだけになるまで、この時点でグループ内のすべての要素が整然としていると見なされ、グループ化は終了します。