拥有稳定性：冒泡排序

labuladong原创约 1558 字

前置知识

阅读本文前，你需要先学习：

一句话总结

冒泡算法是对选择排序的一种优化，通过交换 nums[sortedIndex] 右侧的逆序对完成排序，是一种稳定排序算法。

你可以点开可视化面板，点击播放按钮，然后点击加速/减速按钮调节速度，即可直观感受冒泡排序的过程：

前文讲解了选择排序这种最简单直接的排序算法，其中分析了选择排序的几个待优化的问题：

1、选择排序算法是个不稳定排序算法，因为每次都要交换最小元素和当前元素的位置，这样可能会改变相同元素的相对位置。

2、选择排序的时间复杂度和初始数据的有序度完全没有关系，即便输入的是一个已经有序的数组，选择排序的时间复杂度依然是 $O(n^2)$ 。

3、选择排序的时间复杂度是 $O(n^2)$ ，具体的操作次数大概是 $n^2/2$ 次，常规的优化思路无法降低时间复杂度。

那么本文就围绕着选择排序的种种缺陷，看看能不能想办法帮它解决一下。

重获排序稳定性

前文分析过选择排序失去稳定性的原因，即每次都要交换最小元素（nums[minIndex]）和当前元素（nums[sortedIndex]），这样可能会改变相同元素的相对位置。

你仔细思考这个交换过程，其实它的目标是把 nums[minIndex] 放到到 nums[sortedIndex]，至于 nums[sortedIndex] 这个位置的元素应该去哪里，它并不关心。之所以它用交换操作，只是因为交换操作最简单，不需要涉及数据搬移。

在交换过程中，把 nums[minIndex] 放到到 nums[sortedIndex] 的操作是不影响相同元素的相对顺序的：

[2, 2', 2'', 1, 1']
 ^           ^
[1, 2', 2'', _, 1']
 ^           ^
sortedIndex  minIndex

真正破坏稳定性的，是让 nums[sortedIndex] 去 nums[minIndex] 的位置这一步：

[1, 2', 2'', 2, 1']
 ^           ^

可以看到 2, 2', 2'' 这三个元素的相对顺序被打乱了。

所以优化的方向就在这里，你不要图省事儿直接把 nums[sortedIndex] 交换到 nums[minIndex]，而是模仿在数组中部插入元素的操作，将 nums[sortedIndex..minIndex] 的元素整体向后移动一位，把 nums[sortedIndex + 1] 的位置空出来让 nums[sortedIndex] 这个元素去那里待着。

[2, 2', 2'', 1, 1']
 ^           ^
[1, 2', 2'', _, 1']
 ^           ^
[1, _, 2', 2'', 1']
 ^           ^
[1, 2, 2', 2'', 1']
 ^           ^
sortedIndex  minIndex

可以看到，这次 2, 2', 2'' 和 1, 1' 的相对顺序都没有发生改变，选择排序就变成了稳定排序了。

具体代码如下，只需要把选择排序代码中交换元素的部分换一下即可：

// 对选择排序进行第一波优化，获得了稳定性
void sort(int[] nums) {
    int n = nums.length;
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 在未排序部分中找到最小值 nums[minIndex]
        int minIndex = sortedIndex;
        for (int i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }

        // 交换最小值和 sortedIndex 处的元素
        // int tmp = nums[sortedIndex];
        // nums[sortedIndex] = nums[minIndex];
        // nums[minIndex] = tmp;

        // 优化：将 nums[minIndex] 插入到 nums[sortedIndex] 的位置
        // 将 nums[sortedIndex..minIndex] 的元素整体向后移动一位
        int minVal = nums[minIndex];
        // 数组搬移数据的操作
        for (int i = minIndex; i > sortedIndex; i--) {
            nums[i] = nums[i - 1];
        }
        nums[sortedIndex] = minVal;

        sortedIndex++;
    }
}

你可以拿着这个算法去力扣第 912 题「排序数组」提交一下，虽然最后会超时无法通过，但是可以证明这个算法的正确性是没有问题的。

这个算法对比标准的选择排序，虽然拥有了稳定性，但是执行效率会下降，虽然从 Big O 表示法的角度来看，两层嵌套循环的时间复杂度还是 $O(n^2)$ ，但毕竟又加了一个 for 循环，实际执行次数肯定会大于标准选择排序的 $n^2/2$ 次。

下面我们再来看看，能不能进一步优化，避免这个额外的 for 循环。

优化时间复杂度

仔细观察上面的算法代码，while 循环内部主要做了两件事：

1、第一个 for 循环寻找 nums[sortedIndex..] 中的最小值。

2、第二个 for 循环将这个最小值插入到 nums[sortedIndex] 的位置。

那么我们能否将这两个步骤合在一起呢？具体来说，你在寻找 nums[sortedIndex..] 中的最小值的时候能不能做些力所能及的事情，能不能做到找到最小值后，它就已经被放在正确的位置上，不需要再进行数据搬移了？

答案是可以的，看我操作：

// 对选择排序进行第二波优化，获得稳定性的同时避免额外的 for 循环
// 这个算法有另一个名字，叫做冒泡排序
void sort(int[] nums) {
    int n = nums.length;
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 寻找 nums[sortedIndex..] 中的最小值
        // 同时将这个最小值逐步移动到 nums[sortedIndex] 的位置
        for (int i = n - 1; i > sortedIndex; i--) {
            if (nums[i] < nums[i - 1]) {
                // swap(nums[i], nums[i - 1])
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
            }
        }
        sortedIndex++;
    }
}

这个优化就比较巧妙了，倒序遍历 nums[sortedIndex..]，如果发现逆序对儿，就交换顺序，这样最小值就会逐步移动到 nums[sortedIndex] 的位置。

而且由于我们只交换相邻的逆序对儿，不会去碰值相同的元素，所以这个算法是稳定排序。

这个算法的时间复杂度依然是 $O(n^2)$ ，实际执行次数和选择排序类似，也是一个等差数列求和，大约是 $n^2/2$ 次。

冒泡排序

这个算法的名字叫做冒泡排序，因为它的执行过程就像从数组尾部向头部冒出水泡，每次都会将最小值顶到正确的位置。

提前终止算法

上面说到选择排序的一个问题是，其时间复杂度和初始数据的有序度完全没有关系，即便输入的数组已经有序，选择排序依然会执行 $O(n^2)$ 次操作。

在上面的一些列优化之后，就可以解决这个问题了，具体看代码：

// 进一步优化，数组有序时提前终止算法
void sort(int[] nums) {
    int n = nums.length;
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 加一个布尔变量，记录是否进行过交换操作
        boolean swapped = false;
        for (int i = n - 1; i > sortedIndex; i--) {
            if (nums[i] < nums[i - 1]) {
                // swap(nums[i], nums[i - 1])
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
                swapped = true;
            }
        }
        // 如果一次交换操作都没有进行，说明数组已经有序，可以提前终止算法
        if (!swapped) {
            break;
        }
        sortedIndex++;
    }
}

好了，以上就是针对选择排序的一系列优化，最终使它拥有了排序稳定性，并支持在数组有序时提前终止算法。唯一的遗憾是，时间复杂度依然是 $O(n^2)$ ，并没有降低。

下面我们继续探讨，看看还有什么方法能够改进选择排序。

拥有稳定性：冒泡排序

912. 排序数组 https://leetcode.cn/problems/sort-an-array

912. Sort an Array https://leetcode.com/problems/sort-an-array

重获排序稳定性

优化时间复杂度

提前终止算法