冒泡排序

1.冒泡排序概念

依次比较数组中两个相邻元素的大小，若a[j]>a[j+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排到最后。
重复此操作，直至数组有序。
举个例子：

int[] a = {5, 9, 7, 4, 1, 3, 2, 8};

首先将5与9比较，因为5<9，故数组不变；

再将9与7比较，因为9>7，故交换位置，a={5,7,9}；
.......
第一轮冒泡后的结果：[5, 7, 4, 1, 3, 2, 8, 9]。
冒泡排序即将第一个数与第二个数比较，第二个数与第三个数比较，……

2.编程思路

① 定义数组a，i从0开始遍历至a数组的长度-1，如果a[i]>a[i+1]，则对换位置。否则不变，继续比较下两个数。第一轮冒泡完成；
② 第一轮把最大的数放置最后，在循环体外层继续遍历，记为j，也是从0开始至a数组长度-1；
③ 此时的代码冒泡功能已经实现，不过有待优化，具体见下文。

3.代码实现

package array;

import java.util.Arrays;

/**
 * @author: 邹祥发
 * @date: 2021/10/13 09:28
 * 冒泡排序 -- 简单版
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {5, 9, 7, 4, 1, 3, 2, 8};
        bubble(array);
    }

    public static void bubble(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            //判断位置是否发生交换
            boolean swapped = false;
            for (int j = 0; j < a.length - 1 - i; i++) {
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                    swapped = true;
                }
            }
            System.out.println("一轮冒泡后：" + Arrays.toString(a));
            if (!swapped) {
                //位置不再交换时，退出
                break;
            }
        }
    }

    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

4.优化

优化方式:每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序,直接退出外层循环即可

package array;

import java.util.Arrays;

/**
 * @author: 邹祥发
 * @date: 2021/10/13 10:37
 * 冒泡排序 -- 优化版
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {5, 9, 7, 4, 1, 3, 2, 8};
        bubble(array);
    }

    public static void bubble(int[] a) {
        int n = a.length - 1;
        do {
            //记录最后一次交换索引位置
            int last = 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));
        } while (n != 0);
    }

    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

结果：
第轮冒泡后：[5, 7, 4, 1, 3, 2, 8, 9]
第轮冒泡后：[5, 4, 1, 3, 2, 7, 8, 9]
第轮冒泡后：[4, 1, 3, 2, 5, 7, 8, 9]
第轮冒泡后：[1, 3, 2, 4, 5, 7, 8, 9]
第轮冒泡后：[1, 2, 3, 4, 5, 7, 8, 9]
第轮冒泡后：[1, 2, 3, 4, 5, 7, 8, 9]