『Introduction to Algorithms』という本のクイックソートの章で説明されているクイックソート アルゴリズムは、Hoare-Partitioning を採用していません。
一般的なホア パーティショニングに対するこのアプローチの利点について、誰か教えてください。それとも作者の好みの問題なのでしょうか？
1552 次
1 に答える
6
第 2 版(第 1 版からの変更ログ)のメモには、次のように書かれています (強調してください):
クイックソート (セクション 7.1) に使用される分割方法と、予想される線形時間順序統計アルゴリズム (セクション 9.2) は異なります。現在、Lomuto によって開発された方法を使用しています。これは、インジケーター確率変数とともに 、やや単純な分析を可能にします。ホアレによる初版からの方法は、第7章に問題として現れる。
于 2011-08-02T07:18:49.843 に答える