今天和大家分享的是我系统学习的第一大类算法:排序算法,以前我在写博客的时候总会说:排序算法是我的初恋,所以我的印象很深。
这部分其实可以弄成「我的算法学习路线」的详细版本,计划把知识体系做一个串讲,干脆就叫「特别不严谨」吧。但是限于公众号、手机这样的媒介,我就暂时只说我认为最重要的部分。
大家可以先看看图,然后再看看文字。如果想深入学习排序算法,可以看看《算法(第 4 版)》和《算法导论》的相关章节。
我目前在 B 站的视频只讲到「归并排序」,「归并排序」相关的例题讲解这两天还在赶,肯定要鸽了,真香啊。
今天展示 6 种排序算法:选择排序、冒泡排序、插入排序、希尔排序、归并排序、快速排序。
每一轮 选 出最小的元素交换到数组的前面。
我以前专门找过从来没有学习过算法的朋友,问他怎么给一个数组排序,他给我的回答就是:先选出最小的、再选出第 2 小的、再选出第 3 小的、…… ,这个描述就是「选择排序」。「选择」就这样记下来了。
遍历剩下的、还没有排好序的部分,选出最小元素有一个很形象的名词叫「打擂台算法」,即:通过一次遍历,选出最优者。
两两 比较 相邻 两个位置的元素,把较大的元素交换到上方。每一轮都会把当前最大的元素冒泡到数组的末尾。
我是这样记的:把数组竖着摆放,值越大的最先冒泡上来。
我看到过有一些朋友,把「选择排序」和「冒泡排序」搞混了:
3. 插入排序
插入排序每一次将一个元素 插入 到它前面的有序数组中。实际上有两种插入的方式:
其实这种插入方式更像「插入排序」本来的样子,《算法导论》上的图更形象。
《算法导论》第 2.1 节 插入排序
插入排序有个很重要的特点:数组接近有序的时候,插入排序可以很快完成。「接近有序」的意思是:每个元素和它排序以后最终所在的位置不远。
希尔是计算机科学家的名字,所以希尔排序就得换一个名字来记。
希尔排序是 「分组插入排序」 或者 「带间隔的插入排序」。好处是:让较小的元素一下子来到数组的前面。
每一轮完成一次分组插入排序以后,数组就朝着接近有序的方向前进了一步,最后一轮一定是一次标准的插入排序。
此时数组比未排序的时候更有序了一点。
此时数组比第 2 轮排序开始之前更有序了一点。
提示:「归并排序」和「快速排序」是理解「递归」的很好的学习材料,它们都是「分治思想」的应用。 我最开始学习「选择排序」「插入排序」「希尔排序」「冒泡排序」的时候,还觉得可以慢慢消化。到「归并排序」和「快速排序」的时候就慢来下来了,但是学着学着就发现,还真的有点儿意思,有了「递归」,排序就快了起来。
归并排序的基本思想是「分治算法」。「分治算法」我通常是用「曹冲称象」的故事来理解的。
合并两个有序数组。类似把两个已经按照身高排好序的队伍合并成一队,每次看队伍最前面的同学,选出身高较矮的同学。
「归并排序」总是一分为二,真正在合并两个有序数组的时候完成排序操作。
「快速排序」在如何「分」这件事情上下足了功夫,因为划分足够好,每一次划分能够排定一个元素,所以「快速排序」没有「合并」的过程。
「快速排序」的「分」有一个专门的名词叫 partition
,关于 partition
其实还有蛮多可以说的,以后我们可以单独拿出来再聊聊。
刚开始的时候,我总是在「力扣」上找一些很容易解决的问题,感兴趣很重要。我认为的「容易」有两个标准:
下面罗列了我认为这部分重要的例题。
「归并排序」的例题:
归并排序的经典问题。
逆序数的升级版本,需要借助「索引数组」这个概念,其实就是建立了数值和下标的映射关系。
定义了更强的逆序关系,但实际上依然应用的是求解逆序对的思想:分而治之。
「快速排序」的例题:
这两个问题特别重要,需要深刻理解 partition 和「循环不变量」。
经典的荷兰国旗问题,需要利用「快速排序」 partition 的思想完成。
经典的 TopK 问题,需要深刻理解「快速排序」的 partition 过程。
今天就和大家聊这么多,不知道这种形式的分享是不是能够对大家有一点用。在定稿之前,我还删去了很多内容,希望这样的串讲大家看起来不要太累就好。
有什么好的意见和建议,都可以留言告诉我。
这两天要去录视频了,公众号的更新就不会像最近每天都发,但是话题和想要和大家分享的内容我会一直在准备。
我有严重的完美主义倾向,它是我很严重的缺点,由于性格原因,屡教不改,造成了我做事很没有效率。这两周给自己定下了目标,并且和大家约定好,每天都发(昨天因为传 GIF 图片的原因折腾到凌晨,干脆就早上发出去)。把我以前放在话题箱里的事情都拿出来写写,好在已经完成,但是视频录制那边又耽搁了。
本周以及以后公众号的更新变为不定期,大家给我一些时间调整我的节奏。也欢迎大家对我提出要求,感谢大家的支持、理解和陪伴。