バブル整列(Bubble Sort)

1.泡の位置合わせ

Bubbleソートは、一端から他端に移動し、2つずつ比較します.比較を行う場合、必要に応じて位置を変えることができます.終点に到達すると、終点にある値はソートを終了します.並べ替えが完了したばかりなので、移動する位置を1つ減らす必要があるため、開始位置に移動し直します.
このような手順を繰り返して、位置合わせの値を徐々に増やし、最終的にはすべての要素が位置合わせされます.
元素がN個であれば、最初に(N−1)回比較を行う.そして(N-2)番です...最後に一度だけ比較します.
合計比較オペランドは1+2+...+N-1=(N-1)*N/2.
合計交換演算回数は平均(N-1)*N/4である.
2つの数値を加算した結果はn^2に比例するので,時間的複雑度はO(n^2)である.

2.Javaコード

コードはオブジェクトを体現している.一般的な数字の体現と原理には何の違いもない.ただし、ソート可能なオブジェクトを作成するために、ソートされたPOJOはComparableおよびimplementsになる.compareTo(Object obj)は正数(+)を返すと前後の順序が変わり、負数(-)を返すと順序は変わらない.
Itemクラス

public final class Item implements Comparable<Item> {

    private final int price;

    private Item(int price) {
        this.price = price;
    }

    // Item 객체 생성용 정적 팩토리 메소드
    public static Item valueOf(int price) {
        return new Item(price);
    }

    public int getPrice() {
        return price;
    }

    // 비교 대상인 item의 key(price)가 더 작으면 자리를 바꾸도록 양수(+) 반환 -> 오름차순 정렬
    @Override
    public int compareTo(Item item) {
        return price - item.getPrice();
    }

}

バブルソートクラス

import java.util.Comparator;

public class BubbleSort {

    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static void sort(Object[] arr) {
        for (int end = arr.length - 1; end >= 1; end--) {
            //int swapCount = 0;
            for (int i = 0; i < end; i++) {
                Comparable first = (Comparable) arr[i];
                Comparable second = (Comparable) arr[i + 1];
                if (first.compareTo(second) > 0) {
                    swap(arr, i, i + 1);
                    //swapCount++;
                }
            }
            /*if (swapCount == 0) {
                break;
            }*/
        }
    }

    public static <T> void sort(T[] arr, Comparator<T> comparator) {
        for (int end = arr.length - 1; end >= 1; end--) {
            //int swapCount = 0;
            for (int i = 0; i < end; i++) {
                if (comparator.compare(arr[i], arr[i + 1]) > 0) {
                    swap(arr, i, i + 1);
                    //swapCount++;
                }
            }
            /*if (swapCount == 0) {
                break;
            }*/
        }
    }

    private static void swap(Object[] arr, int i, int j) {
        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

コメントコード
これは、ソートが早期に完了したかどうかを確認するコードです.残りの区間を巡る過程でswapが発生しなかった場合、ソートは完了します.したがって、並べ替えを行う必要はありません.
テスト

public class App {
    public static void main(String[] args) {
        Item item1 = Item.valueOf(50);
        Item item2 = Item.valueOf(20);
        Item item3 = Item.valueOf(70);
        Item item4 = Item.valueOf(100);
        Item item5 = Item.valueOf(10);

        Item[] items = new Item[] { item1, item2, item3, item4, item5 };

        BubbleSort.sort(items);
        System.out.println("오름차순");
        for (Item item : items) {
            System.out.println(item.getPrice());
        }

        System.out.println();

        //i2 > i1이면 양수(+) 리턴하므로 자리가 바뀌어 i2가 앞으로 오게 된다.
        BubbleSort.sort(items, (Item i1, Item i2) -> i2.compareTo(i1));
        System.out.println("내림차순");
        for (Item item : items) {
            System.out.println(item.getPrice());
        }
    }
}

出力結果

오름차순
10
20
50
70
100

내림차순
100
70
50
20
10