用5分钟熟悉3种经典排序算法，浅显易懂!

来源：首席吹牛官（ID：ITman-99）

编辑：妮子小菇凉

若干年前pony在腾讯产品暨技术峰会上就说过：“我们希望的产品经理是从技术晋升而来的。”技术是实施手段，产品最终还是要靠技术来实现，产品还是不能远离技术。

那么不想通过枯燥的代码来理解几大排序算法，本文通过动态可视化图来解析冒泡排序、选择排序及插入排序。

排序算法最终目的是让无序的数据组合变成有序的数据组合。

一、冒泡法

从字面上能理解， “冒泡”即小值的浮上来，大值沉下去。

1. 冒泡排序法基本思路

第一步比较相邻的元素大小。如果第一个比第二个大，就交换两个元素位置。

之后对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

下面先通过图文形式一步一步进行案例拆解。

拿[20，10，15，30，12]这个数组举例。

第一遍循环

检查是否 20 > 10；是，交换元素位置；

检查是否 20 > 15；是，交换元素位置；

检查是否 20 > 30；否，位置不做交换；

检查是否 30 > 12；是，交换元素位置；

第一遍循环结束，此时将最后一个没有排序过的元素标记为已排序（即30）。因为在最近的一次扫描过程中至少有一次交换发生过，我们可以进行另一轮扫描。此轮扫描只需要循环判断前面4个元素。

第二遍循环开始

检查是否 10 大于 15；否，位置不做交换；

检查是否 15 大于 20；否，位置不做交换；

检查是否 20 大于 12； 是，交换元素位置；

此时标记 “20”为已排序，那么同理下一轮循环遍历只需循环判断前面3个元素。

……….

避免视觉疲劳，图文只说明前面2轮循环，下面的3轮循环大家自己思考和理解。

2. 冒泡排序法全流程

3. 冒泡法总结

每一轮左右元素两两比较，不进行跨元素比较

每一轮循环比较都会产生当前最大值（当前最大值：这一轮下来的最大值）

每一轮循环后就会少一个元素进行比较（因为每结束一轮就会产生一个当前最大值）

二、选择排序法

选择排序是从冒泡排序演化而来，每一轮比较得出最小的那个值，然后依次和每轮“无序区”中参与比较的第一个值进行交换。

1. 选择排序法基本思路

初始时在序列中找到最小元素

放到序列的起始位置作为已排序序列

然后再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾

以此类推，直到所有元素均排序完毕

注意选择排序与冒泡排序的区别：

冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最大元素放到合适的位置；而选择排序每循环遍历一次都记住了当前最小元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

下面还是以[20，10，15，30，12]这个数组举例。

第一遍循环

先把最小值设置成为 20 , 然后通过遍历剩下的没有排序过的元素来找到真正的最小值；

检查是否 10 小于现在的最小值 (20)。是，将 10 设为新的最小值；

检查是否 15 小于现在的最小值 (10)。否，10仍然是最小值；

检查是否 30 小于现在的最小值 (10)。否，10仍然是最小值；

检查是否 12 小于现在的最小值 (10)。否，10仍然是最小值。

一轮过后，最小值出现。

交换最小的元素 (10) 和第一个没有排序过的元素 (20)。

现在10是被认定整个数组最小的值。

第二遍循环

把现在的最小值设置成为 20 , 然后通过遍历剩下的没有排序过的元素来找到真正的最小值；

检查是否 15 小于现在的最小值 (20)。是，将 15 设为新的最小值；

检查是否 30 小于现在的最小值 (15)。否，15仍然是最小值；

检查是否 12小于现在的最小值 (15)。是，将 12 设为新的最小值；

交换最小的元素 (12) 和第一个没有排序过的元素 (20)；

数组排序顺序更新为 10 12 15 30 20。

2. 选择排序法全流程

3. 选择排序法总结

每一轮进行跨元素比较

每一轮循环比较都会产生当前最小值（当前最小值：这一轮下来的最小值）

每一轮循环比较后就会少一个元素进行比较（因为每结束一轮就会产生一个当前最小值）

三、插入排序法（直接插入）

插入排序是基于互相比较的排序。所谓的“比较”，就是通过比较数组中的元素，看谁大谁小，根据结果对应调整元素的位置。

1. 插入排序法基本思路

初始时先默认将第一个元素标记为已排序

然后提取第一个没有排序过的元素，找出插入提取元素的地方并和已经排序过的元素进行比较。

比较大小若条件成立，则将已排序过的元素往右移1个单位，如果条件不成立，则在现有位置直接插入。

以此类推，直到所有元素均排序完毕

还以[20，10，15，30，12]这个数组举例

将第一个元素 (20) 标记为已经排序过；

提取第一个没有排序过的元素 (10)；

找出插入提取元素的地方；和已经排序过的元素 20 比较；

20 大于 10 成立, 则将现在已经排序过的元素20向右移动1格；

在数组的最开始（没有东西可以比较），则在现有位置上插入元素。

提取第一个没有排序过的元素 (15)；

找出插入提取元素的地方；和已经排序过的元素 20 比较；

20 大于 15 成立, 则将现在已经排序过的元素20 向右移动1格；

10 大于 15 不成立, 在现有位置上插入一个元素；

提取第一个没有排序过的元素 (30)；

找出插入提取元素的地方；和已经排序过的元素 20 比较。

20 大于 30 不成立, 在现有位置上插入一个元素；

提取第一个没有排序过的元素 (12)。

……..

避免篇幅过大导致视觉疲劳，下面几步大家进行自我思考和理解。

2. 插入排序法全流程

3. 插入排序法总结

由“有序组”和“待插入组”组成

每一轮都有一个待插入对象（可以接收实时数据进行排序）直到“待插入组元素为0”

除了以上三种排序算法，还有许多不同的排序算法，每个都有其自身的优点和使用场景，当然也有局限性。可以多看几遍全流程动态图弄清来龙去脉，理解性地记忆，希望对你有用。

前自带bug程序员，现不知名产品经理，随缘更新~

欢迎留言

本文由首席吹牛官（ID：ITman-99）原创发布，授权互联网早读课转载。内容仅代表作者独立观点，不代表早读课立场。如需转载，请联系原作者。