2

Quucksort 3wayは、配列内の多く/ほとんどの項目が等しい場合に役立つことを目的としています。

私の質問は、一般的な場合にquicksort 3way勝つということquicksortですか?

一般的なケースでは、同等またはそれ以上のアイテムは多くなく、すべてのアイテムが異なるということです。

私はいくつかのベンチマークを行いましたが、私の感じでは、一般的にquicksort 3way、クラシックよりもさらに悪いですquicksort。

4

1 に答える 1

1

少し考えてみてください。別のアルゴリズムの最悪のシナリオを解決するのに役立つように設計されたアルゴリズムがあります。もちろん、一般的なケースでは初期アルゴリズムに勝るものではありません。3 方向クイックソートのアイデアは、平均的なケースではなく、最悪のケースの動作を改善することです。

于 2013-07-22T15:19:49.813 に答える