【基础算法】排序算法 —— 冒泡排序

一、算法原理

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，如果不满足大小关系要求，就进行交换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序。

示例：使用冒泡排序对数组 arr = [4，5，6，3，2，1] 从小到大排序。

第1次冒泡：

第2次冒泡：

第3次冒泡：

第4次冒泡：

第5次冒泡：

第6次冒泡：

冒泡过程回顾

二、冒泡排序算法优化

思路：当某次冒泡操作没有数据交换时，说明数组已经完全有序，不用再进行后续的冒泡操作。

示例：使用冒泡排序对数组 arr = [3，5，4，1，2，6] 从小到大排序。

第1次冒泡：

第2次冒泡：

第3次冒泡：

第4次冒泡：

第4次冒泡操作无数据交换，说明数组已经完全有序，不用再进行后续的冒泡操作。

三、代码实现

/**
 * 冒泡排序：时间复杂度 O(n^2)，空间复杂度 O(1)，稳定
 *
 * @param arr 待排序数组
 */
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    boolean isSwap = false;
    for (int i = 0, len = arr.length; i < len - 1; i++) { // 冒泡操作的次数
        for (int j = 0; j < len - 1 - i; j++) { // 每次冒泡比较的元素
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                isSwap = true;
            }
        }
        // 优化：没有交换代表数组已经完全有序
        if (!isSwap) {
            return;
        }
    }
}

private static void swap(int[] arr, int i, int j) {
    if (i == j) {
        return;
    }
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

四、算法评价

4.1 时间复杂度

最好时间复杂度：O(n)

最好情况下，要排序的数组已经是有序的，只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。

最坏时间复杂度：O(n²)

最坏情况下，要排序的数组刚好是倒序排列的，需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n²)。

平均时间复杂度：O(n²)

平均时间复杂度就是加权平均期望时间复杂度，分析的时候要结合概率论的知识。对于包含 n 个数据的数组，这 n 个数据就有 n! 种排列方式。不同的排列方式，冒泡排序执行的时间肯定是不同的。比如我们前面举的那两个例子，其中一个要进行 6 次冒泡，而另一个只需要 4 次。如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算会很复杂。这里我们通过“有序度”和“逆序度”来进行分析。

冒泡排序包含两个操作原子：比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换的总次数是确定的，即为逆序度，也就是 n*(n-1)/2 - 初始有序度。第1个示例中的数组就是 15 – 3 = 12，要进行 12 次交换操作。

对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n*(n-1)/2 次交换。最好情况下，初始状态的有序度是 n*(n-1)/2，就不需要进行交换。我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n²)，所以平均情况下的时间复杂度就是 O(n²)。这个平均时间复杂度推导过程并不严谨，但是很实用，毕竟概率论的定量分析太复杂，不太好理解。

4.2 空间复杂度

冒泡过程只涉及相邻元素的比较和交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

4.3 稳定性

冒泡排序中，只有交换才会改变两个元素的前后顺序。当相邻的两个元素大小相等时，我们不做交换，所以相同大小的数据在排序前后不会改变顺序，这样就可以保证冒泡排序是稳定的排序算法。