冒泡排序及其优化

1. 冒泡排序思路

ps只是相邻元素比较，别和选择排序搞混了

---

2. 代码实现

2.1 基础做法

public class mao_pao_pai_xu {
    public static void main(String[] args) {
        int[] array = {5, 2, 7, 4, 1, 3, 8, 9};
        bubble(array);
    }

    /**
     * 基础做法
     */
    public static void bubble(int[] a){
        for (int j = 0; j < a.length - 1; j++) {
            for (int i = 0; i < a.length - 1; i++) {
                if (a[i] > a[i+1]) {
                    swap(a, i, i+1);
                }
            }
            System.out.println(Arrays.toString(a));
        }
    }

    /**
     * 置换函数
     */
    public static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

//最终每一次大循环输出，需要循环a.length次
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
[2, 1, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]

---

2.2 优化一

public class mao_pao_pai_xu {
    public static void main(String[] args) {
        int[] array = {5, 2, 7, 4, 1, 3, 8, 9};
        bubble(array);
    }

    /**
     * 优化一：
     * 用一个标识符 swapped 来判断这次小循环是否发生了交换
     * 若没有 则排序完毕 不用继续大循环
     */
    public static void bubble(int[] a){
        for (int j = 0; j < a.length - 1; j++) {
            boolean swapped = false;
            //这个 -j 是每次循环后 都会把最大的放到后面，就可以少比较一次
            for (int i = 0; i < a.length - 1 - j; i++) {
                if (a[i] > a[i+1]) {
                    swap(a, i, i+1);
                    swapped = true;
                }
            }
            if (!swapped) break;
            System.out.println(Arrays.toString(a));
        }
    }

    /**
     * 置换函数
     */
    public static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

//最终只需要四次大循环
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
[2, 1, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]

---

2.3 优化二

public class mao_pao_pai_xu {
    public static void main(String[] args) {
        int[] array = {5, 2, 7, 4, 1, 3, 8, 9};
        bubble(array);
    }

    /**
     * 优化二：
     * 每一次循环时都记录下 最后一次 交换的位置下标，因为如果后面都没有交换，就说明后面的已经排序好了
     * 减少了小循环的次数，达到优化目的
     * 下一次则不需要到下标之后的位置上去
     */
    public static void bubble2(int[] a){
        int n = a.length - 1;
        while (n != 0) {
            int last = 0;//这里必须要等于0 最后一次循环时才会使n = 0
            for (int i = 0; i < n; i++) {
                if (a[i] > a[i+1]) {
                    swap(a, i, i+1);
                    last = i;
                }
            }
            n = last;
            System.out.println(Arrays.toString(a));
        }
    }
    /**
     * 置换函数
     */
    public static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

//和优化一一样只要四次大循环，但是我们观察小循环的次数
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
[2, 1, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]

//二
[2, 5, 7, 4, 1, 3, 8, 9]
[2, 5, 7, 4, 1, 3, 8, 9]
[2, 5, 4, 7, 1, 3, 8, 9]
[2, 5, 4, 1, 7, 3, 8, 9]
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 5, 4, 1, 3, 7, 8, 9]
大[2, 5, 4, 1, 3, 7, 8, 9]
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 4, 5, 1, 3, 7, 8, 9]
[2, 4, 1, 5, 3, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
大[2, 4, 1, 3, 5, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
[2, 1, 4, 3, 5, 7, 8, 9]
[2, 1, 3, 4, 5, 7, 8, 9]
大[2, 1, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
大[1, 2, 3, 4, 5, 7, 8, 9]

//一
[2, 5, 7, 4, 1, 3, 8, 9]
[2, 5, 7, 4, 1, 3, 8, 9]
[2, 5, 4, 7, 1, 3, 8, 9]
[2, 5, 4, 1, 7, 3, 8, 9]
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 5, 4, 1, 3, 7, 8, 9]
大[2, 5, 4, 1, 3, 7, 8, 9]
[2, 5, 4, 1, 3, 7, 8, 9]
[2, 4, 5, 1, 3, 7, 8, 9]
[2, 4, 1, 5, 3, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
大[2, 4, 1, 3, 5, 7, 8, 9]
[2, 4, 1, 3, 5, 7, 8, 9]
[2, 1, 4, 3, 5, 7, 8, 9]
[2, 1, 3, 4, 5, 7, 8, 9]
[2, 1, 3, 4, 5, 7, 8, 9]
[2, 1, 3, 4, 5, 7, 8, 9]
大[2, 1, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
大[1, 2, 3, 4, 5, 7, 8, 9]