0

バブルソート用の次のコードがありますが、まったくソートされていません。ブール値を削除すると、正常に機能します。私の a[0] は他のすべての要素よりも小さいため、スワップが実行されていないことを理解しています。

package com.sample;

public class BubleSort {
    public static void main(String[] args) {
        int a[] = { 1, 2, 4, 5, 6, 88, 4, 2, 4, 5, 8 };
        a = sortBuble(a);
        for (int i : a) {
            System.out.println(i);
        }

    }

    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 = 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

3 に答える 3

2

これは本質的にあなたのものと同じですが、機能し、より効率的です:

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-10T06:56:40.037 に答える
1

あなたのバブルソートは間違っていますか？

    private static int[] sortBuble(int[] a) {
        boolean swapped = true;
        int n = a.length;
        for (int i = 0; i < n && swapped; i++) {
            swapped = false;
            int newn = 0;
            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;
                    newn = j;
                }
            }
            n = newn;
        }

        return a;
    }
于 2013-11-10T06:39:00.120 に答える
0

これはフラグ付きバブルソートと呼ばれます。主に時間の節約に役立ちます。配列の位置がソートされているかどうかをチェックします。ソートされると壊れ、2回目の実行に移ります。

コードは次のように書き換えることができます:-

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;             
            }
        }
        if(!swapped)
           break;
    }
于 2018-03-12T11:59:09.413 に答える