安定した並べ替えアルゴリズムは何ですか?-よくある問題-php.cn

安定した並べ替えアルゴリズムは何ですか?

奋力向前

リリース： 2021-09-28 18:58:53

オリジナル

27870 人が閲覧しました

安定したソートアルゴリズムには、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 が両方とも歩けない場合、

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]が入れ替わる瞬間に不安定になります。

5. マージソート

マージソートは、シーケンスを短いシーケンスに再帰的に分割します。再帰的な終了は、短いシーケンスが

1## のみを持つことです。 # 個の要素 (直接順序付けされていると考えてください) または

2 シーケンス (1 の比較と交換) を実行し、順序付けされた各セグメントシーケンスを順序付けされた長いシーケンスにマージし、元のシーケンスになるまでマージを続けます。すべて並べ替えました。 1 または 2 要素がある場合、1 要素は交換されず、2 要素は交換されないことがわかります。サイズが等しい場合に交換されます。意図的に交換しているわけではないため、安定性が損なわれることはありません。 では、短い順序のシーケンスをマージする過程で、安定性は破壊されるのでしょうか?

いいえ、マージプロセス中に、現在の 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 つの同一の要素は破壊されます。したがって、ヒープソートは安定したソートアルゴリズムではありません。