私は素敵な教科書（役に立たなかった）とオンラインを調べてみました。私がコーメンによって取り組んでいる本によると、配列の最初の要素をピボットとして使用することになっています。最初の要素がたまたま 1 であるため、どうすればよいか困っています。
配列は次のようになります:
[1, 16, 2, 3, 14, 5, 12, 7, 10, 8, 9, 17, 19 、21、23、26、27]
繰り返しになりますが、この本のアルゴリズムの問題は、最初の要素をピボットとして選択することです。そして、1 を他のすべての要素と比較し、それ以下の要素が他にないことがわかったら、ピボットとサブ配列の中央の要素を交換します。左側のサブ配列はピボットよりも小さいです。右側のサブアレイはピボットよりも大きくなっています。しかし、ピボットが 1 の場合、交換する方法はありません。本当に混乱しています。どんな助けでも素晴らしいでしょう。本のタイトルは、誰かがそれに精通している場合に備えて、Introduction to Algorithms, 3rd Edition です。
質問する
965 次
2 に答える
8
通常の場合と違いはありません。左側の部分を空として扱い、1 からの部分配列である右側の部分でクイックソートを実行します。
これは特別なケースではありません。実際、入力がソートされると、単純なクイックソートはO(N^2)ソート アルゴリズムに退化します。ウィキペディアの引用：
クイックソートの非常に初期のバージョンでは、パーティションの左端の要素がピボット要素として選択されることがよくありました。残念ながら、これは既にソートされた配列で最悪の動作を引き起こします。これはかなり一般的な使用例です。この問題は、ピボットのランダム インデックスを選択するか、パーティションの中間インデックスを選択するか、(特に長いパーティションの場合) ピボットのパーティションの最初、中間、および最後の要素の中央値を選択することで簡単に解決されました ( R.セッジウィック）。
于 2013-06-03T21:25:50.803 に答える
2
3 のルールとして知られているものを使用できます。配列の最初の値、中間の値、および最後の値を選択し、それらのいずれかをピボット候補として選択します。これは、最高のピボットが得られることを保証するものではありませんが、本当に悪いピボットが得られる可能性を低くします。
于 2013-06-03T21:25:16.267 に答える