Java排序01-冒泡排序

1. 比较相邻的元素，如果前者比后者大，那就交换这二者的顺序。
2. 从头到尾遍历，对每一对相邻元素都进行比较并按需交换。这步做完后，最后的元素将会是最大的元素。
3. 重复步骤2，此时只需要遍历到（n-1）个位置，因为最后一个元素已经是最大了，无需比较。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度O(n²)，空间复杂度O(1)

Java实现代码如下，主要使用第二种方法：

public class S01_BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1, 5, 8, 3, 0, 4, 2, 7, 9, 6};
        bubbleSort1(arr);
        bublleSort2(arr);
        bublleSort3(arr);
    }

    //冒泡排序常规思路
    public static void bubbleSort1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        System.out.println("冒泡排序：");
        for (int i = 0; i < arr.length; i++) {
            //设定一个标记，若为true，则表示此次循环没有进行交换，也就是带排序列已经有序，排序已经完成
            //boolean flag = false;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int tmp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = tmp;
                }
            }
        }

        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
    }

    //优化冒泡排序
    public static void bublleSort2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        System.out.println("优化冒泡排序：");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
    }

    //继续优化冒泡排序
    public static void bublleSort3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        System.out.println("继续优化冒泡排序：");
        //设定交换标志，如果有正确顺序的元素则不需要交换
        boolean flag = true;
        //若flag为true，说明有数据交换，否则停止循环
        for (int i = 0; i < arr.length && flag; i++) {
            //初始设置为false
            flag = false;
            //注意j是从后往前循环的
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    //如果有数据交换，则flag为true
                    flag = true;
                }
            }
        }
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
    }
}