一般的に使用される並べ替えアルゴリズムの動的図の説明

この記事では、視覚的に直感的で、一定の参考価値があるいくつかの一般的に使用される並べ替えアルゴリズムを主に使用します。興味のある友人はそれを参照できます

具体的な内容は次のとおりです

1 クイック並べ替え

はじめに:

クイックソートは、Tony Hall によって開発されたソートアルゴリズムです。平均して、n 個の項目を並べ替えるには、O(n log n) 個の比較が必要です。最悪の場合、O(n2) 回の比較が必要になりますが、この状況は一般的ではありません。実際、クイックソートは、多くの場合、他の Ο(n log n) アルゴリズムよりも大幅に高速です。これは、その内部ループがほとんどのアーキテクチャで効率的に実装でき、ほとんどの現実世界のアプリケーションで適切に機能するためです。データによって設計の選択が決定され、二次項の可能性が低減されます。必要な時間内に。

手順:

シーケンスから「ピボット」と呼ばれる要素を選択します。
シーケンスを並べ替えます。ピボット値より小さいすべての要素はピボットの前に配置され、ピボット値より大きいすべての要素はピボットの後ろに配置されます。ピボットの前 ベースの後ろ (どちらの側にも同じ番号を付けることができます)。このパーティションが終了すると、塩基はシーケンスの途中になります。これをパーティション操作と呼びます。
基本値より小さい要素の部分配列と基本値より大きい要素の部分配列を再帰的に並べ替えます。

並べ替え効果:

2 マージソート

はじめに:

マージソート (マージソート、台湾語訳: マージソート) は、マージ操作に基づいた効果的な並べ替えアルゴリズムです。このアルゴリズムは、分割統治法 (pide と Conquer) を使用する非常に典型的なアプリケーションです。

ステップ:

サイズが 2 つのソートされたシーケンスの合計になるようにスペースを適用します。 このスペースは、マージされたシーケンスを保存するために使用されます
としましょう。 2 つのポインターを設定します。初期位置は、2 つのソートされたシーケンスの開始位置です。2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージ スペースに配置し、ポインターを次の位置に移動します。ステップ 3. 特定のポインターがシーケンスの最後に到達するまで、他のシーケンスの残りのすべての要素をマージされたシーケンスの最後に直接コピーします。 並べ替え効果:

) は、次のようなデータ構造を使用して設計された並べ替えアルゴリズムを指します。ヒープ。ヒープは、完全なバイナリ ツリーに近似し、ヒープ プロパティを満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードより小さい (または大きい) ものです。

手順:

(さらに複雑です。オンラインで確認してください)

並べ替え効果:

4 選択並べ替え

はじめに:

選択並べ替えは、シンプルで直感的な並べ替えアルゴリズムです。仕組みは次のとおりです。まず、ソートされていないシーケンスの中で最小の要素を見つけて、それをソートされたシーケンスの先頭に格納します。次に、引き続きソートされていない残りの要素から最小の要素を見つけて、それをソートされたシーケンスの最後に置きます。すべての要素がソートされるまで続きます。

並べ替え効果:

5 バブルソート

はじめに:

バブルソート（バブルソート、台湾語訳：バブルソートまたはバブルソート）は、単純な並べ替えアルゴリズムです。ソート対象のシーケンスを繰り返し調べて、一度に 2 つの要素を比較し、順序が間違っている場合はそれらを交換します。配列を訪問する作業は、それ以上の交換が必要なくなるまで繰り返されます。これは、配列がソートされたことを意味します。このアルゴリズムの名前は、小さい要素がスワッピングによって配列の先頭にゆっくりと「浮動」するという事実に由来しています。

手順:

隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。

隣接する要素の各ペアに対して、最初のペアから始めて最後のペアで終わるまで、同じことを行います。この時点では、最後の要素が最大の数値である必要があります。

最後の要素を除くすべての要素に対して上記の手順を繰り返します。 比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

並べ替え効果:

6 挿入並べ替え

紹介:

Insertion Sort のアルゴリズムの説明は、シンプルで直感的な並べ替えアルゴリズムです。ソートされていないデータの場合は、ソートされたシーケンスを後ろから前にスキャンし、対応する位置を見つけて挿入します。挿入ソートの実装では、通常、インプレース ソートが使用されます (つまり、O(1) 個の余分なスペースのみを使用するソート)。したがって、後ろから前へのスキャン プロセス中に、ソートされた要素を繰り返して徐々に行う必要があります。後方にシフトされ、最新の要素の挿入スペースが提供されます。

手順:

ソートされたと考えられる最初の要素から開始します
次の要素を取り出し、既にソートされた一連の要素を後ろから前にスキャンします
要素（ソート済み）が大きい場合は、新しい要素、要素を次の位置に移動します
並べ替えられた要素が新しい要素以下になる位置が見つかるまでステップ 3 を繰り返します
その位置に新しい要素を挿入します
ステップ 2 を繰り返します

7 ヒルソート

はじめに:

ヒルソートは、降順増分ソートアルゴリズムとも呼ばれ、挿入ソートの高速かつ安定した改良版です。

ヒルソートは、挿入ソートの次の 2 つの特性に基づいて改良された方法を提案します:

挿入ソートは、ほぼソートされたデータを操作する場合に非常に効率的です。つまり、線形ソートの効率を達成できます
しかし、挿入ソートは一般的に言えば、挿入ソートは一度に 1 ビットしかデータを移動できないため、非効率的です

ソート効果:

以上が一般的に使用される並べ替えアルゴリズムの動的図の説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。