安定したソート アルゴリズムには、1. バブル ソート、2. 選択ソート、3. 挿入ソート、4. クイック ソート、5. マージ ソート、6. 基数ソート、7. ヒル ソート (シェル)、8 . ヒープソート。
このチュートリアルの動作環境: Windows 10 システム、Dell G3 コンピューター。
一般的な並べ替えアルゴリズムの安定性を分析し、それぞれの簡単な理由を説明します。
安定したソート アルゴリズム:
1. バブル ソート
バブル ソート バブル並べ替えとは、小さな要素を前方に移動したり、大きな要素を後方に移動したりすることです。比較は隣接する 2 つの要素の比較であり、これら 2 つの要素間でも交換が行われます。したがって、2 つの要素が等しい場合、退屈にそれらを交換することはないと思います。
2 つの等しい要素が隣接していない場合、前のペアごとの交換で 2 つが隣接していても、今回は交換されないため、同じ要素の順序は変更されていません。リスク バブル ソートは安定したソート アルゴリズムです。
2. 選択の並べ替え
選択の並べ替えでは、各位置の最小の現在の要素が選択されます。たとえば、最初の位置で最小の要素が選択され、次の位置の中で最小の要素が選択されます。残りの要素。2 番目の要素として 2 番目に小さい要素を選択し、n-1
番目の要素まで続きます。n 番目の要素は、残っている唯一の最大要素であるため、選択する必要はありません。次に、選択において、現在の要素がある要素より小さく、その小さな要素が現在の要素と等しい要素の後に出現する場合、交換後の安定性は破壊されます。
は発音が少し難しいです。たとえば、シーケンス 5 8 5 2 9
では、1
番目の要素 5# を選択するとわかります。最初のパスの ## が
2 と交換されると、元のシーケンス内の
2
5 の相対的な順序が破棄されるため、選択の並べ替えは行われません。安定したソートアルゴリズム。
3. 挿入ソート
挿入ソートは、すでに順序付けられた小さなシーケンスに基づいて、一度に 1 つの要素を挿入します。もちろん、最初は、この小さな順序付けられたシーケンスには要素が 1 つだけあり、それが最初の要素でした。比較は、順序付けられたシーケンスの最後から始まります。つまり、挿入する要素が、既にソートされている最大の要素と比較されます。要素がそれより大きい場合は、その要素のすぐ後ろに挿入します。それ以外の場合は、挿入するまで前方を探し続けます。挿入する必要がある要素を見つけます。 挿入された要素と等しい要素が見つかった場合、挿入された要素は、挿入する要素を等しい要素の後に配置します。 つまり、等しい要素の順序は変わっておらず、元の順序なしシーケンスからの順序がソート順となるため、挿入ソートは安定します。4. クイック ソート
クイック ソートには 2 つの方向があります。左側の添字 i は右端まで進みます。a[i] の場合<= a[center_index]、ここで
center_index は center 要素の配列添字であり、通常は配列の
0 要素として解釈されます。
a[j]>a[center_index] の場合、右側の添え字
j は左端まで移動します。
i<=j、
a[i] と
a[j] を交換し、繰り返します。以上の処理を
i>j まで行います。
a[j] と
a[center_index] を入れ替えて、簡単な並べ替えを完了します。中心要素が
a[j] と交換されると、前の要素の安定性が損なわれる可能性が非常に高くなります。たとえば、シーケンスは
5 3 3 4 3 8 9 10 11# になります。 ##、ピボット要素 5
と 3
(5
番目の要素、添え字は 1
から始まります) を交換すると、要素を変更する 3 安定性が崩れるため、クイックソートは不安定なソートアルゴリズムであり、中心要素とa[j]が入れ替わる瞬間に不安定になります。
マージ ソートは、シーケンスを短いシーケンスに再帰的に分割します。再帰的な終了は、短いシーケンスが
1## のみを持つことです。 # 個の要素 (直接順序付けされていると考えてください) または2 シーケンス (
1 の比較と交換) を実行し、順序付けされた各セグメント シーケンスを順序付けされた長いシーケンスにマージし、元のシーケンスになるまでマージを続けます。すべて並べ替えました。
1 または
2 要素がある場合、
1 要素は交換されず、
2 要素は交換されないことがわかります。サイズが等しい場合に交換されます。意図的に交換しているわけではないため、安定性が損なわれることはありません。
では、短い順序のシーケンスをマージする過程で、安定性は破壊されるのでしょうか?
6. 基数ソート
基数ソートでは、まず低位でソートしてから収集します。
次に高位でソートしてから収集します。 ;などを最高の位置まで続けます。一部の属性には優先順位が設定されている場合があります。属性は、最初に優先度の低い順に並べ替えられ、次に優先度の高い順に並べ替えられます。最終的な順序は、優先度の高い属性が最初になり、同じ高い優先順位と低い優先順位を持つ属性が最初になります。基数ソートは個別のソートと個別のコレクションに基づいているため、安定したソート アルゴリズムです。
7. ヒル ソート (シェル)
ヒル ソートは、異なる同期長に従って要素を挿入し、並べ替えることです。ステップサイズが最も大きいため、挿入ソートの要素数が少なく、非常に高速です。
要素が基本的に順序付けされており、ステップ サイズが小さい場合、順序付けされたシーケンスに対して挿入ソートは非常に効率的です。したがって、Hill ソートの時間計算量は O(n^2)
よりも優れています。複数の挿入ソートにより、1 つの挿入ソートは安定しており、同じ要素の相対的な順序は変更されないことがわかっていますが、異なる挿入ソート プロセスでは、同じ要素がそれぞれの挿入ソートで移動する可能性があり、最終的にはその安定性が低下します。変更. がスクランブルされているため、シェルソートが不安定です。
8. ヒープのソート
ヒープの構造は、ノード i
の子が 2 * i であることを知っています。
および 2 * i 1
ノードの場合、大きな上部ヒープには親ノードがその 2
子ノード以上である必要があり、小さな上部ヒープには親ノードが必要です。ノードはその 2
子ノード以下である必要があります。長さ n
のシーケンスで、ヒープのソート プロセスは、n / 2
から始まる最大 (最大) の値とその子ノードの合計 3
を選択します。ヒープ) または最小 (小さな上部ヒープ)、これらの 3
要素のどちらを選択しても、安定性が損なわれることはありません。ただし、n / 2-1
、n/2-2
、...1
の要素を選択すると、安定性が破壊されます。 n/2
番目の親ノードが次の要素を交換する一方で、n/2-1
番目の親ノードが次の同じ要素を交換しない可能性があります。その場合、間の安定性は次のようになります。これら 2 つの同一の要素は破壊されます。したがって、ヒープ ソートは安定したソート アルゴリズムではありません。
関連知識の詳細については、FAQ 列をご覧ください。
以上が安定した並べ替えアルゴリズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。