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

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

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

1. 将数组划分成前后两个子集：{[order-list], [unorder-list]}，前面是有序集，后面是无序集
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. 边界选值前插入，前满后空则终止。

代码仓库在这里[2]，点击阅读原文可达，欢迎通过提 issue 来告诉我你想看图解的常见面试题目，如果发现有疏漏，也欢迎提 PR 来贡献。

参考资料

[1]

Procreate: https://procreate.com/

[2]

infra 面试基础 repo: ：https://github.com/DistSysCorp/infra-interview