ヒープソートは安定していますか?

ヒープソート、クイックソート、ヒルソート、直接選択ソートは不安定なソートアルゴリズムですが、基数ソート、バブルソート、直接挿入ソート、半挿入ソート、マージソートは不安定です。安定したソートアルゴリズム。

ヒープのソート

ヒープの構造は、ノード i の子が 2*i ノードと 2*i 1 ノードであることを知っています。大きなトップ ヒープでは、親ノードが以下である必要があります。 2 つの子ノード以上であること。スモールトップヒープでは、親ノードがその 2 つの子ノード以上であることが必要です。ヒープでは、親ノードがその 2 つの子ノード以下であることが必要です。

長さ n のシーケンスで、ヒープのソートのプロセスは、n/2 番目とその子ノードから開始して最大 (大きな上部ヒープ) または最小 (小さな上部ヒープ) を選択します。合計は次のとおりです。 3 つの値 要素を選択しても安定性が損なわれることはありません。ただし、n /2-1、n/2-2、...1 個の親ノードの要素を選択すると、安定性が損なわれます。

n/2 番目の親ノードが次の要素を交換し、n/2-1 番目の親ノードが次の同じ要素を交換しない可能性があり、この場合、これら 2 つの同じ要素間の安定性は破壊されます。したがって、ヒープ ソートは安定したソート アルゴリズムではありません。

以上がヒープソートは安定していますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。