若干年前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轮循环大家自己思考和理解。
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”
除了以上三种排序算法，还有许多不同的排序算法，每个都有其自身的优点和使用场景，当然也有局限性。可以多看几遍全流程动态图弄清来龙去脉，理解性地记忆，希望对你有用。
本文由 @动物园园长 原创发布于人人都是产品经理。未经许可，禁止转载
题图来自 Pexels ，基于 CC0 协议
给作者打赏，鼓励TA抓紧创作！ 赞赏 5人打赏
