冒泡排序（Bubble Sort）是一种基础的交换排序。

所谓交换排序就是通过元素的两两比较，判断是否符合要求，如果不符合则交换元素位置来达到排序的目的。冒泡排序因为交换的过程类似水冒泡而得名，小（大）的元素经过不断的交换由水底慢慢的浮到水的顶端。

思路

从第一个数开始，依次比较相邻的两个数，将小的数往后排，经过一轮排序最小的数会被冒泡至队尾，确定位置。按此方法，对未确定位置的元素再一轮比较，每轮确定一个数的位置，直到最后队列中所有数都确定自己的位置。

示例：

假设有一个数组，内部元素为 3，4，1，5，2

第一轮排序

比较第 1 第 2 个元素：4 > 3，交换位置比较第 2 第 3 个元素：1 < 3，不交换比较第 3 第 4 个元素：5 > 1，交换位置比较第 4 第 5 个元素：2 > 1，交换位置

经过第一轮排序后的数组为：4，3，5，2，1，数组最后位置的元素确定为数组最小的元素

第二轮排序

比较第 1 第 2 个元素：3 < 4，不交换比较第 2 第 3 个元素：5 > 3，交换位置比较第 3 第 4 个元素：2 < 3，不交换

经过第二轮排序后的数组为：4，5，3，2，1，确定数组最后两个位置的元素

第三轮排序

比较第 1 第 2 个元素：5 > 4，交换位置比较第 2 第 3 个元素：3 < 4，不交换

经过第三轮排序后的数组为：5，4，3，2，1，确定数组最后三个位置的元素

第四轮排序

比较第 1 第 2 个元素：4 < 5，不交换

经过第四轮排序后的数组为：5，4，3，2，1，全部元素确定位置

JAVA实现

public class BubbleSort {    public static void sort(int[] arr) {        int len = arr.length - 1;        for (int i = 0; i < len; i++) {            for (int j = 0; j < len - i - 1; j++) {                if (arr[j] < arr[j + 1]) {                    int temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                }                System.out.println("第" + (i+1) + "轮，第" + (j+1) + "次:" + print(arr));            }            System.out.println("第" + (i+1) + "轮:" + print(arr));            System.out.println("---------------------------------");        }    }    public static void main(String[] args) {        int[] arr = new int[] { 3, 4, 1, 5, 2 };        System.out.println("排序前:" + print(arr));        sort(arr);        System.out.println("排序后:" + print(arr));    }    private static String print(int[] arr) {        return Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(" "));    }}

结果输出如下

排序前:3 4 1 5 2第1轮，第1次:4 3 1 5 2第1轮，第2次:4 3 1 5 2第1轮，第3次:4 3 5 1 2第1轮，第4次:4 3 5 2 1第1轮结果:4 3 5 2 1---------------------------------第2轮，第1次:4 3 5 2 1第2轮，第2次:4 5 3 2 1第2轮，第3次:4 5 3 2 1第2轮结果:4 5 3 2 1---------------------------------第3轮，第1次:5 4 3 2 1第3轮，第2次:5 4 3 2 1第3轮结果:5 4 3 2 1---------------------------------第4轮，第1次:5 4 3 2 1第4轮结果:5 4 3 2 1---------------------------------排序后:5 4 3 2 1

最好时间

最坏时间

平均时间

额外空间

稳定性

O(n）

O(n2)

O(n2)

1

稳定

优缺点：

1、实现简单

2、即使正序，虽然不需要进行交换，但比较次数没有减少，通过优化可以实现 O(n) 的最好时间

算法优化

在上例中，第三轮其实就已经完成了排序，但程序依然需要进行第四轮比较，当一轮比较结束没有发生数据交换，就说明排序已经完成。

public class BubbleSort {    public static void sort(int[] arr) {        int len = arr.length - 1;        for (int i = 0; i < len; i++) {            // 设置一个标识位            boolean flag = true;            for (int j = 0; j < len - i - 1; j++) {                if (arr[j] < arr[j + 1]) {                    int temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                    // 如果发生数据交换，则转换标识位                    flag = false;                }                System.out.println("第" + (i+1) + "轮，第" + (j+1) + "次:" + print(arr));            }            System.out.println("第" + (i+1) + "轮结果:" + print(arr));            System.out.println("---------------------------------");            // 如果一轮比较过后，没有发生数据交换，则跳出循环            if (flag) {                break;            }        }    }    public static void main(String[] args) {        int[] arr = new int[] { 5, 4, 3, 2, 1 };        System.out.println("排序前:" + print(arr));        sort(arr);        System.out.println("排序后:" + print(arr));    }    private static String print(int[] arr) {        return Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(" "));    }}

输出结果如下，此时只进行一轮比较

排序前:5 4 3 2 1第1轮，第1次:5 4 3 2 1第1轮，第2次:5 4 3 2 1第1轮，第3次:5 4 3 2 1第1轮结果:5 4 3 2 1---------------------------------排序后:5 4 3 2 1

最后关注一下