クイックソートのアイデアは、ピボットを選択し続けることです。そして、左側にあるピボットよりも大きい値を、右側にあるピボットよりも小さい値と交換します。参照: ref
次の場合に何が起こるかを100％確認したいだけです：
- ピボットより大きい左の値なし、ピボットより小さい右の値
- 左の値はピボットより大きく、右の値はピボットより小さくありません
- ピボットより大きい左の値なし、ピボットより小さい右の値なし
2 に答える
0
スワップ基準は実装によって異なります。あなたが言及した3つのケースで何が起こるかは、パーティション分割スキームによって異なります。クイックソートには多くの実装がありますが、(私の意見では) 最もよく知られている主な 2 つの実装は次のとおりです。
Hoare's Partition: 最初の要素はピボットで、2 つのインデックス変数 (
iおよびj) は配列 (a[]) を中心に向かって歩きますが、それらが遭遇する要素はピボットよりも小さい/大きいです。次にa[j]、 とa[i]が入れ替わります。この実装では、ピボットと等しい要素に対してスワップが発生することに注意してください。これは、配列に同一のエントリが多数含まれている場合に重要であると考えられています。iとjcross の後a[0]が と交換されるa[j]ため、ピボットは小さいか等しいパーティションと大きいか等しいパーティションの間になります。ロムートの仕切り。これは、現在の Wiki クイックソート エントリの「インプレース バージョン」の下に疑似コードで実装されたものです。ここで、ピボットは何でも (中央値、または 3 の中央値など)、 の最後の要素と交換され
aます。ここでiは、配列の最後に向かってのみ「歩きます」:a[i]>=pivotスワップされてa[j]デクリメントjされるたびに。最後に、ピボットはa[i+1]
（例については、ここを参照してください）。
Robert Sedgewickは、配列が 3 つのパーティション (ピボットよりも小さい、等しい、ピボットより大きい) に分割される3 方向のパーティショニング スキームを支持しています。実装はまだ異なります（上記のリンクを参照）。
于 2013-04-02T02:38:45.593 に答える