【图解面试基础】三种基本排序算法

这是使用 Procreate 画图之余,心血来潮开的一个面试基础系列,力求图文并茂、代码视频兼顾,做成最好看的面试系列。欢迎喜欢的小伙伴点赞、转发和打赏,如果支持的同学多,我就继续更下去。

3-basic-sort.png

作者:木鸟杂记 https://www.qtmuniao.com/2023/09/18/three-basic-sort 转载请注明出处

{[order-list], [unorder-list]}

冒泡排序、选择排序和插入排序是三种最基本的排序算法。其原理是相通的:

  1. 将数组划分成前后两个子集:前面是有序集,后面是无序集
  2. 三种方法都是线性的一次从无序集中搬一个元素到有序集中,只不过搬法不同:
    • 冒泡:从无序集最后逐个比较冒一个到有序集最后
    • 选择:遍历无序集,选一个放到有序集最后
    • 插入:从边界处选一个,插入到有序集中合适位置

三种排序的复杂度都是 O(n^2)。

冒泡排序

S-order <–bubble– S-unorder

像冒泡一样,每次让最小的数冒出剩余数据集(无序)“水面”,抵达有序集。

口诀:

  1. 数组分两块,初始前空置;
  2. 后面交换往前挤,前满后空则终止。

选择排序

S-order <–selection– S-unorder

从剩余数据集(无序)中选择最值,放到有序集中。

口诀:

  1. 数组分两块,初始前空置;
  2. 后面选极前追加,前满后空则终止。

插入排序

S-order <–insertion– S-unorder

从剩余数据集(无序)中随意取一个值,然后通过比较“插入”(也可以理解为往前冒泡)到有序集中。

口诀:

  1. 数组分两块,初始前空置;
  2. 边界选值前插入,前满后空则终止。

代码仓库在这里,欢迎通过提 issue 来告诉我你想看图解的常见面试题目,如果发现有疏漏,也欢迎提 PR 来贡献。

b 站视频在这里:https://www.bilibili.com/video/BV1du41177iu
Youtube 视频:https://www.youtube.com/playlist?list=PLSISRu2b2N55Htp_3tUQoqMPP4EsTLGxv


最后,如果喜欢我的文章,可以订阅我的小报童付费专栏《系统日知录》,专注互联网最基础的方向——大规模数据系统,有图数据库、代码解读、优质英文播客翻译、数据库学习、论文解读等等系列,欢迎喜欢我文章的朋友订阅👉专栏支持,你的支持对我持续创作优质文章非常重要。


我是青藤木鸟,一个喜欢摄影、专注大规模数据系统的程序员,欢迎关注我的公众号:“木鸟杂记”,有更多的分布式系统、存储和数据库相关的文章,欢迎关注。 关注公众号后,回复“资料”可以获取我总结一份分布式数据库学习资料。 回复“优惠券”可以获取我的大规模数据系统付费专栏《系统日知录》的八折优惠券。

我们还有相关的分布式系统和数据库的群,可以添加我的微信号:qtmuniao,我拉你入群。加我时记得备注:“分布式系统群”。 另外,如果你不想加群,还有一个分布式系统和数据库的论坛(点这里),欢迎来玩耍。

wx-distributed-system-s.jpg