算法与数据结构在我眼中的样子（1）排序算法

今天和大家分享的是我系统学习的第一大类算法：排序算法，以前我在写博客的时候总会说：排序算法是我的初恋，所以我的印象很深。

这部分其实可以弄成「我的算法学习路线」的详细版本，计划把知识体系做一个串讲，干脆就叫「特别不严谨」吧。但是限于公众号、手机这样的媒介，我就暂时只说我认为最重要的部分。

大家可以先看看图，然后再看看文字。如果想深入学习排序算法，可以看看《算法（第 4 版）》和《算法导论》的相关章节。

我目前在 B 站的视频只讲到「归并排序」，「归并排序」相关的例题讲解这两天还在赶，肯定要鸽了，真香啊。

今天展示 6 种排序算法：选择排序、冒泡排序、插入排序、希尔排序、归并排序、快速排序。

1. 选择排序

每一轮 选 出最小的元素交换到数组的前面。

我以前专门找过从来没有学习过算法的朋友，问他怎么给一个数组排序，他给我的回答就是：先选出最小的、再选出第 2 小的、再选出第 3 小的、…… ，这个描述就是「选择排序」。「选择」就这样记下来了。

遍历剩下的、还没有排好序的部分，选出最小元素有一个很形象的名词叫「打擂台算法」，即：通过一次遍历，选出最优者。

2. 冒泡排序

两两 比较 相邻 两个位置的元素，把较大的元素交换到上方。每一轮都会把当前最大的元素冒泡到数组的末尾。

我是这样记的：把数组竖着摆放，值越大的最先冒泡上来。

我看到过有一些朋友，把「选择排序」和「冒泡排序」搞混了：

• 「冒泡排序」每一轮的确是选出最值，但它是通过两两比较和交换，把最值元素逐步地交换到数组的末尾；
• 「选择排序」每一轮选出最小值，一下子交换到数组的前面，二者最大的区别是：选择排序每一轮只交换一次，选择排序的交换次数最少。

3. 插入排序

插入排序每一次将一个元素 插入 到它前面的有序数组中。实际上有两种插入的方式：

• 第 1 种：逐个交换到前面（待插入元素逐个交换到前面） 下图演示了整个插入排序的过程。

• 第 2 种：先暂存再后移（先暂存待插入元素，然后前面比暂存元素严格大的后移） 下图只演示了把 3 插入它前面的有序数组 [1, 2, 4, 5] 的过程。

其实这种插入方式更像「插入排序」本来的样子，《算法导论》上的图更形象。

《算法导论》第 2.1 节 插入排序

插入排序有个很重要的特点：数组接近有序的时候，插入排序可以很快完成。「接近有序」的意思是：每个元素和它排序以后最终所在的位置不远。

4. 希尔排序

希尔是计算机科学家的名字，所以希尔排序就得换一个名字来记。

希尔排序是 「分组插入排序」 或者 「带间隔的插入排序」。好处是：让较小的元素一下子来到数组的前面。

每一轮完成一次分组插入排序以后，数组就朝着接近有序的方向前进了一步，最后一轮一定是一次标准的插入排序。

• 第 1 轮：把下标间隔为 5 的元素分成一组，一共 5 组，分别执行插入排序

此时数组比未排序的时候更有序了一点。

• 第 2 轮：把下标间隔为 2 的元素分成一组，一共 2 组，分别执行插入排序

此时数组比第 2 轮排序开始之前更有序了一点。

• 第 3 轮：把下标间隔为 1 的元素分成一组，其实就是标准的插入排序。

提示：「归并排序」和「快速排序」是理解「递归」的很好的学习材料，它们都是「分治思想」的应用。 我最开始学习「选择排序」「插入排序」「希尔排序」「冒泡排序」的时候，还觉得可以慢慢消化。到「归并排序」和「快速排序」的时候就慢来下来了，但是学着学着就发现，还真的有点儿意思，有了「递归」，排序就快了起来。

5. 归并排序

归并排序的基本思想是「分治算法」。「分治算法」我通常是用「曹冲称象」的故事来理解的。

合并两个有序数组。类似把两个已经按照身高排好序的队伍合并成一队，每次看队伍最前面的同学，选出身高较矮的同学。

6. 快速排序

「归并排序」总是一分为二，真正在合并两个有序数组的时候完成排序操作。

「快速排序」在如何「分」这件事情上下足了功夫，因为划分足够好，每一次划分能够排定一个元素，所以「快速排序」没有「合并」的过程。

「快速排序」的「分」有一个专门的名词叫 partition，关于 partition 其实还有蛮多可以说的，以后我们可以单独拿出来再聊聊。

经典问题

刚开始的时候，我总是在「力扣」上找一些很容易解决的问题，感兴趣很重要。我认为的「容易」有两个标准：

• 不需要任何算法知识，就可以解决的问题；
• 思想很简单，代码我只需要模仿就好了。

下面罗列了我认为这部分重要的例题。

「归并排序」的例题：

• 《剑指 Offer》 第 51 题：逆序数

归并排序的经典问题。

• 「力扣」第 315 题：计算右侧小于当前元素的个数

逆序数的升级版本，需要借助「索引数组」这个概念，其实就是建立了数值和下标的映射关系。

• 「力扣」第 493 题：翻转对

定义了更强的逆序关系，但实际上依然应用的是求解逆序对的思想：分而治之。

「快速排序」的例题：

这两个问题特别重要，需要深刻理解 partition 和「循环不变量」。

• 「力扣」第 75 题：颜色分类

经典的荷兰国旗问题，需要利用「快速排序」 partition 的思想完成。

• 「力扣」第 215 题：数组的第 K 大元素

经典的 TopK 问题，需要深刻理解「快速排序」的 partition 过程。

今天就和大家聊这么多，不知道这种形式的分享是不是能够对大家有一点用。在定稿之前，我还删去了很多内容，希望这样的串讲大家看起来不要太累就好。

有什么好的意见和建议，都可以留言告诉我。

闲聊

这两天要去录视频了，公众号的更新就不会像最近每天都发，但是话题和想要和大家分享的内容我会一直在准备。

我有严重的完美主义倾向，它是我很严重的缺点，由于性格原因，屡教不改，造成了我做事很没有效率。这两周给自己定下了目标，并且和大家约定好，每天都发（昨天因为传 GIF 图片的原因折腾到凌晨，干脆就早上发出去）。把我以前放在话题箱里的事情都拿出来写写，好在已经完成，但是视频录制那边又耽搁了。

本周以及以后公众号的更新变为不定期，大家给我一些时间调整我的节奏。也欢迎大家对我提出要求，感谢大家的支持、理解和陪伴。