0

誰かが私が間違っていることを説明できますか? k番目に小さい要素を見つけたいのですが、何かがうまくいかない)

例: ソートされていない配列 int[] uA = { 2, 9, 4, 13, 11, 7, 8 };があります。「9」をピボット要素として使用し、パーティティング（クイックソート）の最初の繰り返しの後、この配列{2、8、4、7、11、13、9}を取得します。中央のポインターが「11」に表示される場所。そして、それはどういう意味ですか？すべての要素が 11 よりも 11 大きいわけではありません。また、11 は「適切な場所」にあるわけではありません。しかし、たとえば、5 番目に小さい要素 (11) を返したいとします。

4

2 に答える 2

1

ピボットが適切な場所にありません。パーティション分割の最後にピボットを適切な場所に配置して、ピボットの位置を確認する必要があります。(真ん中の要素を気にする必要はありません) 次に、この情報を使用して、K 番目に小さい要素を計算できます。分割の最後にピボットが x 番目のインデックスにあるとします。

K = x =>  pivot is the right answer
K < x =>  the answer is in the left partition, search left partition  
K > x =>  the answer is in the right partition, search right partition
于 2012-11-01T21:22:03.970 に答える
0

コードにエラーが見つかりました。パーティション分割部分で2つの要素を交換した後、クイックソートのようにポインター（左++、右-）を移動しましたが、移動しないでください。

たくさんのご来場ありがとうございました！

于 2012-11-02T11:50:53.447 に答える