1

2つのバブルアルゴリズムを見つけましたが、どちらが正しいかわかりません...

最初の例：

for (int i = 1; i < input.Length-1; i++)
    for (int j = 0; j < input.Length - 1 - i; j++)
        if (input[j] > input[j + 1])
            swap(input, j, j + 1);

2番目の例：

for (int i = 1; i < input.Length-1; i++)
    for (int j = 0; j < input.Length - 1; j++)
        if (input[j] > input[j + 1])
            swap(input, j, j + 1);

ウィキペディアの例

入力用：5 1 4 2 8

最初の例：6つの比較

2番目の例：12の比較

ファーストパス：

（5 1 4 2 8）->（1 5 4 2 8）、5>1からスワップ

（1 5 4 2 8）->（1 4 5 2 8）、5>4からスワップ

（1 4 5 2 8）->（1 4 2 5 8）、5>2からスワップ

（1 4 2 5 8）->（1 4 2 5 8）

セカンドパス：

（1 4 2 5 8）->（1 4 2 5 8）

（1 4 2 5 8）->（1 2 4 5 8）、4>2 <-例1はここで停止するのでスワップ

（1 2 4 5 8）->（1 2 4 5 8）

（1 2 4 5 8）->（1 2 4 5 8）

サードパス

（1 2 4 5 8）->（1 2 4 5 8）

（1 2 4 5 8）->（1 2 4 5 8）

（1 2 4 5 8）->（1 2 4 5 8）

（1 2 4 5 8）->（1 2 4 5 8）<-例2ここで停止

編集：私がどちらが正しいかを言うとき、私はどちらが元のバブルソートであるかを意味します

4

6 に答える 6

2

最初のアルゴリズムが正しくありません。配列の最後の要素が最大でない場合は失敗します。

具体的には、「j」の反復：

for (int j = 0; j < input.Length - 1 - i; j++)

最後の要素をスキップするようです。入力が{0、2、2、1}の場合、input.Length = 4

上記のforループの条件はj<4--1 --iです。ここで、i=1なのでj<4--1 -1なので、j <2なので、最後に使用されたjはj = 1になり、最後の比較が入力されます[1]> input [2]->input[3]は決して比較されません。

forループをj<=input.Length --1--iに変更することで修正できます

于 2012-11-29T17:33:47.403 に答える
1

2つのバブルアルゴリズムを見つけましたが、どちらが正しいかわかりません。

どちらも正しいと思います。唯一の違いは、2番目のコードが最後にソートされた配列をループする必要があることです。

于 2012-11-29T17:13:45.317 に答える
1

どちらも正しいです。

最初のものは比較的効率的です。

于 2012-11-29T17:14:32.717 に答える
1

あまり考えずに、どちらも正しいように見えますが、最初の方が冗長な操作が少ないようで、実行にかかる時間が短くなります。

最初のものはあなたの最後のiブロックが正しいという事実に依存しているように思われるので、それはそれらを気にすることさえありません。

于 2012-11-29T17:15:13.157 に答える
1

バブルソートでは、最初のパスの後、最大値が配列の最後の位置を占めることが保証されます。これは、定義上、バブルソートが配列の最後に向かって最大値を交換するためです。

これは、2番目のパスで、最後の値を再度比較する必要がないことを意味します。これは、最後の値が次に低いインデックスの要素以上であることが保証されているためです。同様に、パス2の後、上位2つの要素が最も高い値になり、相互に並べ替えられます。

ひいては、iパス後、i上部の要素は正しい位置に配置されます。

i最初の例では、最大jイテレータ値から減算することにより、これを考慮に入れています。2番目の例では、後続のパスで上位要素を不必要に比較します。害はありませんが、冗長です。つまり、最適化されていません。隣接する値を交換し、より高い値の要素を配列の最後に移動するため、これは依然としてバブルソートです。

それは理にかなっていますか？

于 2012-11-29T17:23:15.553 に答える
1

1つ目は、いわゆる最適化されたバブルソートです。

http://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort

2つ目は、「クラシック」なバブルソートです。

于 2012-11-29T17:23:53.560 に答える