0

これは生計を立てているプログラマーへの質問です -
私は (マスター定理を使用して) クイックソートを使用し、分割する部分配列の中央値になるようにピボットを選択すると (中央値アルゴリズムの中央値を使用して) 証明したところです。 Θ(n) 最悪の場合の実行時間) の場合、クイックソートの最悪の場合の実行時間は Θ(n lg n) です。つまり、基本的にこれは、このバージョンのクイックソートが可能な限り優れていることを意味します。

私の質問は今です - 実際にこのようなクイックソートを実装している人はいますか? それとも、実際には実生活では良くない、素晴らしい理論的なことの 1 つにすぎないのでしょうか?

追伸 - 私が述べていることの証明は必要ありません。これが広く知られている/有用であるかどうかを知りたいだけです

4

3 に答える 3

4

これは知られています (ウィキペディアのエントリを参照してください) が、実際には最悪のケースは比較的まれであるため、平均的なケースでの O(N) 選択アルゴリズムのオーバーヘッドの追加は、一般的に許容できないと考えられています。

于 2013-05-05T14:42:04.230 に答える
1

それは本当にあなたが働いている場所に依存します。これまでのところ、個人的には実際に実装したことはありませんが、職場の要件によって異なると思います.

于 2013-05-05T14:38:06.263 に答える