0

私はデータを持っています (3 はピボットです):

281374

2 つのポインターを左右から移動します

最初に2と4があるので、何も交換しません

それから私は8と7を持っているので、交換して持っています:

273184

今、私は3と1でピンターを持っているので、交換します:

271384

現在、左ポインター = 右ポインター - 1 なので、これらをすばやく並べ替える必要があります。

271 | 384

別々ですよね？

しかし、もしそうなら、私はこのようなものを得るでしょう:

127 | 348

これはソートされたデータではありません！

私は何を間違えたのですか？

4

4 に答える 4

0

クイックソートはそのようには機能しません

3 がピボットの場合:

ピボット（3）を最後に交換します

281374 -> 281473

281473
-

2 は 3 より小さいですか? はい、でもすでに左側にあるのでそのままにしておきます

281473
 -

8 は 3 より小さいですか? いいえ、次の正しい場所を見つける必要があります。リストをたどり、最初の項目 <= ピボット (ピボット自体の場合もあります) を交換します。この場合、その1ように....

281473 -> 218473

今、私たちは

218473
  -

ソートされるまで繰り返します。

于 2013-06-24T14:24:00.823 に答える
0

左が右よりも大きい場合は、対応する数値を交換しません。ピボット値との比較に応じて交換します。 7すでにピボット値よりも大きいため、すでにピボットの正しい (右側) 側にあります。

ただし、インプレース パーティショニングの標準アルゴリズムは、試みているように見えるものとはかなり異なります。インプレース Quicksort に関するウィキペディアの記事をご覧ください。

于 2013-06-24T14:14:16.943 に答える