一、概述

冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为 O（n²）,稳定排序算法。

定义：越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样。

二、冒泡排序图解

冒泡排序是一种交换排序，循环所有元素，根据降序升序判断元素大小是否交换。

图片

上图是按从小到大方式排序。绿色元素为循环下标, 当前下标元素arr[i]>arr[i+1], 则两元素交换位置。第一轮循环结束后，数组中最大的元素已经被移到最后的位置。同理，第二轮循环结束，数组中第二大的元素已经被移到倒数第二的位置。经过n-1次循环，得到最终结果。

三、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) {

    int[] arr = new int[]{1, 3, 2, 4, 9, 7, 5};
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

四、优化

上图我们可以发现第二轮循环结束，数组已经整体有序，然而根据上面的代码逻辑还需循环到n-1次才结束，既然第二轮已经有序，那可以提前结束循环。

结束循环的前提是要知道数组有序，当第n轮循环没发生元素交换，此时已经可以确认当前数组有序，可以增加一个是否发送交换的标识，假设没有发送交换即可结束循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean isSwap = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                isSwap = true;
            }
        }
        // 第(i+1)轮没发送元素交换，数组有序提前结束循环
        if (!isSwap) {
           break; 
        }
    }
}

五、稳定排序算法

当前有数组[2, 1, 3, 3, 5]， 经过某算法排序后数组变得有序，其中存在相同的元素3，如果相同的两个元素3没有经过交换，当前使用的排序算法为稳定排序算法。

冒泡排序相同的元素是不发送交换的，所以冒泡排序是稳定排序算法。