バブルソート-java

バブルソート-java
転載は出典を明記してください.http://blog.csdn.net/a740169405/article/details/50716134
アイデア:
泡の順序付けの思想は小さい数を後ろから一つ一つ前に交換して、水中の気泡のようにずっと上に出たいと思っています.
サイクルインプリメンテーションを使用するには、次の手順に従います.

/** *               */
private static void bubbleSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    boolean isChange;
    int count = arr.length;
    for (int i = 0; i < count; i++) {
        isChange = false;
        for (int j = count - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                change(arr, j, j - 1);
                isChange = true;
            }
        }
        if (!isChange) {
            break;
        }
    }
}

ここでisChangeの判断を加えるのはソートの効率を高めるためであり,一度の比較で交換が発生しなかった場合は,現在は既に順序付けされており,その後の比較は不要であることを示している.
再帰方式:

/** *               * @param arr    * @param tag         */
private static boolean bubbleSort(int[] arr, int tag) {
    if (arr == null || tag < 0 || tag >= arr.length) {
        return false;
    }
    int count = arr.length;
    boolean isChange = false;
    for (int j = count - 1; j > tag; j--) {
        if (arr[j] < arr[j - 1]) {
            change(arr, j, j - 1);
            isChange = true;
        }
    }
    return isChange && bubbleSort(arr, ++tag);
}

交換方法:

/** *                */
private static void change(int[] arr, int l, int r) {
    int tmp = arr[l];
    arr[l] = arr[r];
    arr[r] = tmp;
}

呼び出しコード:

int[] array = new int[] {3, 7, 4, 56, 34, 12, 90, 67, 24};
int[] arr = new int[] {1, 45, 78, 23, 12, 98, 150, 1, 45};
bubbleSort(array);
System.out.println(Arrays.toString(array));
bubbleSort(arr, 0);
System.out.println(Arrays.toString(arr));

結果:
複雑度分析:最良の場合:1回だけ循環比較、すなわちn-1、定数項を除去し、最後にn最悪の場合:配列は逆配列であり、この場合の比較回数はである.もちろん、交換が必要な回数もこれだけ多く、定数項を除去し、最高乗の定数を除去し、複雑度nを得る²
すなわち,発泡ソートの時間的複雑さはnとnである²の間
安定性分析:
バブルソートとは、小さな要素を前に調整したり、大きな要素を後ろに調整したりすることです.比較は隣接する2つの要素の比較であり、交換もこの2つの要素の間で発生する.だから、もし2つの要素が同じなら、あなたはもう退屈に彼ら二人を交換しないと思います.2つの等しい要素が隣接していない場合、前の2つの交換によって2つが隣接していても交換されないため、同じ要素の前後の順序は変わらないので、バブルソートは安定したソートアルゴリズムである.