3

クイックソートについて少し質問があります。配列の最小値または最大値が選択されている場合、配列サイズが 1 つだけ減少するため、パーティションのピボット値は非常に非効率的です。

ただし、その配列の中央値を選択するコードを追加すると、Ii がより効率的になると思います。パーティション アルゴリズムは既に O(N) であるため、O(N log N) アルゴリズムが得られます。

これはできますか？

4

1 に答える 1

8

線形時間の中央値選択アルゴリズムを使用して、クイックソートでピボットを計算できます。これにより、最悪の場合の O(n log n) ソート アルゴリズムが得られます。

ただし、線形時間選択の定数係数は非常に高くなる傾向があるため、結果として得られるアルゴリズムは、実際には、反復ごとにピボットをランダムに選択するだけのクイックソートよりもはるかに遅くなります。したがって、このような実装は一般的ではありません。

O(n 2 ) の最悪のケースを回避するためのまったく異なるアプローチは、introsortのようなアプローチを使用することです。このアルゴリズムは、クイックソートの再帰的な深さを監視します。アルゴリズムが劣化し始めているように見える場合は、最悪の場合の O(n log n) が保証された別のソート アルゴリズム (通常はヒープソート) に切り替えます。これにより、パフォーマンスを著しく低下させることなく、アルゴリズム全体が O(n log n) になります。

お役に立てれば！

于 2012-08-27T19:34:48.507 に答える