经典排序算法之冒泡排序

力扣 912 题（排序数组），是一道适合练习各种排序方式的题。今天本想把部分排序算法一一实现一下，结果发现刚写冒泡就出问题了。

为了加深印象，我做了两个个违背祖宗懒惰的决定，一是一定要重新拾起写博客的习惯，二是用 Canvas 把排序算法做成动画。

我的错误版本 ​

首先，看下我的错误版本的代码：

function sortArray(nums: number[]): number[] {
    for (let i=0; i<nums.length-1; i++) {
        for (let j=i+1; j<nums.length; j++) {
            if (nums[i] > nums[j]) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
            }
        }
    }

    return nums;
}

配上我做的动画：

动画中，前两轮的逻辑我已经标注出来了，可以看出该算法的基本逻辑是，从每轮找出第 i 小的数，放到 i 的位置，最小值确实也是"冒泡"到了前面。 可以看出我这个实际上不是冒泡，而是有点接近选择排序，选择排序是找出最小值后，在一轮循环结束后再进行交换。 而我的这个算法，是每次遇到较小值后就进行交换，因此，我的算法不如选择排序。

它比真正的冒泡排序好吗？ ​

如果你注意到动画的最后一帧，注意看我特意设置的重复项来验证排序是否稳定，原本 480' 是排在 480 后面的，但是在完成排序后，480' 反而跑到了相对前面的位置。

这是由于在和较小值交换时，前面的 480 就有可能被交换到 480' 的后面，从而相对顺序被破坏。

而我们知道，冒泡排序是稳定的，因为冒泡排序中，只有左边的数字大于右边的数字时才会发生交换，相等的数字之间不会发生交换，所以它是稳定的。

所以，我的错误写法还丢失了冒泡排序的稳定的优势。

复杂度方面，同样的实际复杂度，交换的次数也是一样的，所以我的算法没有任何意义。

正确写法 ​

我们可以先查询一下维基百科对冒泡排序算法的描述：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

由此给出实现并不困难：

function sortArray(nums: number[]): number[] {
    for (let i=0; i<nums.length; i++) {
        for (let j=0; j<nums.length-1-i; j++) {
            if (nums[j] > nums[j+1]) {
                [nums[j], nums[j+1]] = [nums[j+1], nums[j]];
            }
        }
    }

    return nums;
}

动画是这样的：

可以从图中看出，每一轮结束，是最大值会出现在正确的位置。而且相同的元素的相对位置是正确的。

反思 ​

从两种实现来看，代码太像了，我原本的解法估计是看网上某处学来的，本质还是自己理解的不到位。

如果面试遇到这种简单排序，写完发现结果是正确的，很容易认为自己的算法是正确的，会非常危险。

所以网上学东西还是需要注意，更倾向于去看一些权威的资料，更要有自己的理解。