一半人写不出冒泡排序？现在我相信了

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天我们继续来解读《算法》第四版这本书，讲完了二分法和并查集之后，我们正式来到了本书的第二大章节——排序。

说到排序不得不提当初轮子哥在知乎里的一个著名评论，他说当年他毕业面试的时候，一半的同学连冒泡排序都写不出来。听起来好像非常夸张，但实际上很正常，早几年的时候，计算机毕业的学生会去做程序员技术岗的可能本身就不到一半。不过在看这本书的时候，我有了一个可怕的发现，我虽然想得起来冒泡排序的原理，但上次写它已经是十几年前的事了……

所以今天就和大家温故而知新，简单回忆复习一下选择排序、冒泡和插入排序这两个入门的排序算法。

选择排序

选择排序的原理非常简单，对于从小到大的排序算法来说，它的第一个元素一定是最小的。既然如此，那么我们就遍历整个数组，找到最小的那个元素，把它放在首位。其次，第二个元素一定是次小的，我们继续遍历剩下的数组，找到剩下元素当中最小的元素，将它放在第二位。

我们可以发现，每一次我们都是从一系列元素当中找到最小的那一个，所以这一段逻辑是可以复用的，我们重复N次，就可以将数组完成排序了。

不难证明，我们一共遍历了

次元素，所以这是一个

的算法。

代码大概是这样的：

void select_sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (nums[j] < nums[i]) swap(nums[i], nums[j]);
        }
    }
}

插入排序

选择排序我们写好了，那么插入排序又是怎样的呢？

选择排序我们每次找到的是剩余元素的最小值，插入排序则是模拟打扑克的过程，我们每次抓到一张新牌之后，总是将它插入到合适的位置，整个排序的过程模拟的就是不停地抓牌插入的过程。

但不一样的是，在数组当中插入元素涉及到移动元素，比如我们在下标2的位置插入一个新元素。那么我们需要将2以后的位置全部向右移动一位，空出一个空位来才行。所以我们说数组插入元素的复杂度是

，就是因为涉及到移动元素。

如果我们正常实现算法，需要先遍历要插入的元素，再找到合适的位置，再移动元素。这里已经三重循环了，复杂度达到了

，超出了我们的预期，我们需要进行优化。怎么优化呢？我们不再是寻找合适的位置再插入，而是从末尾开始向前比对，如果新元素更小就和对比的数交换位置。这样的话，我们就只需要两重循环就可以完成排序过程了。

void insert_sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        for (int j = i; j >-1 && nums[j] < nums[j-1] ; j--) {
            swap(nums[j], nums[j-1]);
        }
    }
}

冒泡排序

冒泡排序的原理和插入排序其实非常类似。

什么叫冒泡排序呢，我们每次遇到新元素就将它和之后的元素比，如果它比之后的元素大，则交换位置，继续再和之后的元素比。这样依次进行的时候，大的元素就像是水泡一样，从前往后冒出来，因此称为冒泡排序。不得不说这个算法名字也是非常形象了。

如果我们来看代码的话，会发现它的代码和插入排序有相似的部分：

void bubble_sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-1-i; j++) {
            if (nums[j] > nums[j+1]) swap(nums[j], nums[j+1]);
        }
    }
}

对于插入排序来说，i的左侧是有序的部分，我们每次循环一次，i向右移动一位，表明我们左侧有序的部分长度增加了1。而冒泡排序当中，有序的部分换到了i的右侧，我们每次循环一次，右侧有序的部分长度增加了1。

今天介绍的这三种排序算法都是

的算法，大体上思路也比较直观和接近，属于比较初级的排序方法。也是很多人入门学的第一个算法，这三种算法都算不上难，但想要把当中的差别和原理理清楚，还是需要花一定心思的。不少人只是浅尝辄止就放弃了，正好这一次我们复习《算法》一书，不妨趁此机会巩固巩固。

好了，今天这篇文章就先聊到这里，感谢大家的阅读。

喜欢本文的话不要忘记三连~