(Python) 二次ソート

二次ソート

バブル方式（バブルソート）、または単純交換によるソート）。

このジャンルの不朽の名作。アクションの原則は単純です。並べ替えられていない隣接する要素を同時に交換しながら、配列を最初から最後まで一周します。最後の場所への最初のパスの結果、「ポップアップ」最大要素。ここで、配列のソートされていない部分 (最初の要素から最後から 2 番目の要素まで) を再度バイパスし、途中でソートされていない隣接要素を変更します。 2 番目に大きい要素は、最後から 2 番目の場所になります。同じ精神で続けて、減少し続ける配列のソートされていない部分をバイパスし、見つかった最大値を最後までプッシュします。
 

並べ替えを挿入

並べ替えを挿入 –これは非常に単純ですが非効率なアルゴリズムですが、他の多くの一般的に効率的なアルゴリズムが開発された後でも、このアルゴリズムを意味のあるものにするいくつかの特定の利点があります。

挿入ソートを使用すると、ソートの前に配列全体を事前に用意する必要はありません。アルゴリズムは、並べ替え中に一度に 1 つの要素を受け取ることができます。これは、 並べ替え中に要素を追加する必要がある場合に非常に便利です。 アルゴリズムは、「再実行」せずに新しい要素を正しい場所に挿入します。配列全体を並べ替えます。

挿入ソートは、小さい (要素数 10 個程度) データセットで効率が良いため、実際に使用できます。

問題は、配列の一部がすでにソートされており、順序を維持しながら配列の残りの要素をソートされた部分に挿入したいということです。これを行うには、アルゴリズムの各ステップで入力データ要素の 1 つを選択し、入力データ セット全体が並べ替えられるまで、配列の既に並べ替えられた部分の目的の位置にそれを挿入します。入力配列から次の要素を選択する方法は任意ですが、通常 (安定した並べ替えアルゴリズムを得るために)、要素は入力配列に出現する順序で挿入されます。

このアルゴリズムのアルゴリズム実装

<プレ> // null 要素は、すでにソートされたシーケンスとみなされます。 // したがって、ループは 1 から始まります I=1 ～ N-1 のループ ステップ 1 X=A[I] J=I WHEN J>0 AND A[J-1]>X //挿入する場所を探しています 交換A[J]、A[J-1] J=J-1 エンドバイ A[J]=X 次へ 計算複雑さ: \(\displaystyle O(n^{2})\)。