2

バブルソートの2つの実装がありますが、そのうちの1つは正常に機能し、もう1つはこれら2つの違いを説明できません

最初のものはこれでうまくいきます

private static int[] sortBuble(int[] a) {
        boolean swapped = true;
        for (int i = 0; i < a.length && swapped; i++) {
            swapped = false;
            System.out.println("number of iteration" + i);

            for (int j = 1; j < a.length; j++) {

                if (a[j - 1] > a[j]) {
                    int temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
                    swapped = true;
                }
            }
        }

        return a;
    }

2つ目はこれは機能しませんが、多かれ少なかれ同じように見えます

private static int[] sortBuble1(int[] a) {
        boolean swapped = true;
        for (int i = 0; i < a.length && swapped; i++) {
            swapped = false;
            System.out.println("number of iteration" + i);

            for (int j = i + 1; j < a.length; j++) {

                if (a[i] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    swapped = true;
                }
            }
        }

        return a;
    }
4

2 に答える 2

3

それらは同じではありません。2 番目の例では、内側の for ループの反復ごとに i 定数を保持しa[i]、比較に使用していますが、これは正しくありません。他の回答で述べたように、最初のものも非効率的です。以下は、最初のものの最適化されたバージョンです。

private static int[] bubblesort(int[] nums)
{
    boolean done = false;

    for (int i = 0;  i < nums.length && !done; i++)
    {
        done = true;

        for (int j = nums.length-1; j > i; j--)
        {
            if (nums[j] < nums[j-1])
            {
                int temp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = temp;
                done = false;
            }
        }
    }

    return nums;
}

i番目の繰り返しの終わりに、最初の i 個の要素がソートされていることがわかっているので、それらを見る必要はもうありません。続行する必要があるかどうかを判断するには、ブール値が必要です。スワップが行われない場合は、完了です。ブール値を削除しても機能しますが、効率は低下します。

于 2013-11-10T07:05:02.140 に答える
1

違いは、配列に使用されるインデックスにあります。

最初のケースでは、内側のforループ withjは から独立していiます。また、jスワップ中に隣接する値を使用するため、配列内の隣接する値が常にスワップされます。

2 番目のケースでは、内側のforループはjから始まりますi + 1。そして、配列のインデックスにiとの両方を使用しています。jしたがって、実際には隣接する要素を比較しているのではなく、遠く離れている可能性のある要素 (たとえば wheni=1とj=4) を比較しています。これはバブル ソートではなく、このアルゴリズムはそのようには機能しません。

于 2013-11-10T07:06:33.043 に答える