走进开发,5分钟熟悉3种经典排序算法 – 互联网运营

产品经理

走进开发,5分钟熟悉3种经典排序算法


若干年前pony在腾讯产品暨技术峰会上就说过:“我们希望的产品经理是从技术晋升而来的。”技术是实施手段,产品最终还是要靠技术来实现,产品还是不能远离技术。那么不想通过枯燥的代码来理解几大排序算法,本文通过动态可视化图来解析冒泡排序、选择排序及插入排序。

走进开发,5分钟熟悉3种经典排序算法

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

一、冒泡法

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

1. 冒泡排序法基本思路

  • 第一步比较相邻的元素大小。如果第一个比第二个大,就交换两个元素位置。
  • 之后对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

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

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

第一遍循环

  • 检查是否 20 > 10;是,交换元素位置;
  • 检查是否 20 > 15;是,交换元素位置;
  • 检查是否 20 > 30;否,位置不做交换
  • 检查是否 30 > 12;是,交换元素位置;

走进开发,5分钟熟悉3种经典排序算法

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

第二遍循环开始

  • 检查是否 10 大于 15;否,位置不做交换;
  • 检查是否 15 大于 20;否,位置不做交换;
  • 检查是否 20 大于 12; 是,交换元素位置;

走进开发,5分钟熟悉3种经典排序算法

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

……….

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

2. 冒泡排序法全流程

走进开发,5分钟熟悉3种经典排序算法

3. 冒泡法总结

  • 每一轮左右元素两两比较,不进行跨元素比较
  • 每一轮循环比较都会产生当前最大值(当前最大值:这一轮下来的最大值)
  • 每一轮循环后就会少一个元素进行比较(因为每结束一轮就会产生一个当前最大值)

二、选择排序法

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

1. 选择排序法基本思路

  • 初始时在序列中找到最小元素
  • 放到序列的起始位置作为已排序序列
  • 然后再从剩余未排序元素中继续寻找最小元素,放到已排序序列的末尾
  • 以此类推,直到所有元素均排序完毕

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

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

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

第一遍循环

  • 先把最小值设置成为 20 , 然后通过遍历剩下的没有排序过的元素来找到真正的最小值;
  • 检查是否 10 小于现在的最小值 (20)。是,将 10 设为新的最小值;
  • 检查是否 15 小于现在的最小值 (10)。否,10仍然是最小值;
  • 检查是否 30 小于现在的最小值 (10)。否,10仍然是最小值;
  • 检查是否 12 小于现在的最小值 (10)。否,10仍然是最小值。

一轮过后,最小值出现。

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

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

走进开发,5分钟熟悉3种经典排序算法

第二遍循环

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

  • 检查是否 15 小于现在的最小值 (20)。是,将 15 设为新的最小值;
  • 检查是否 30 小于现在的最小值 (15)。否,15仍然是最小值;
  • 检查是否 12小于现在的最小值 (15)。是,将 12 设为新的最小值;
  • 交换最小的元素 (12) 和第一个没有排序过的元素 (20);

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

走进开发,5分钟熟悉3种经典排序算法

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

2. 选择排序法全流程

走进开发,5分钟熟悉3种经典排序算法

走进开发,5分钟熟悉3种经典排序算法

3. 选择排序法总结

  • 每一轮进行跨元素比较
  • 每一轮循环比较都会产生当前最小值(当前最小值:这一轮下来的最小值)
  • 每一轮循环比较后就会少一个元素进行比较(因为每结束一轮就会产生一个当前最小值)

三、插入排序法(直接插入)

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

1. 插入排序法基本思路

  • 初始时先默认将第一个元素标记为已排序
  • 然后提取第一个没有排序过的元素,找出插入提取元素的地方并和已经排序过的元素进行比较。
  • 比较大小若条件成立,则将已排序过的元素往右移1个单位,如果条件不成立,则在现有位置直接插入。
  • 以此类推,直到所有元素均排序完毕

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

  • 将第一个元素 (20) 标记为已经排序过;
  • 提取第一个没有排序过的元素 (10);
  • 找出插入提取元素的地方;和已经排序过的元素 20 比较;
  • 20 大于 10 成立,  则将现在已经排序过的元素20向右移动1格;
  • 在数组的最开始(没有东西可以比较),则在现有位置上插入元素。

走进开发,5分钟熟悉3种经典排序算法

  • 提取第一个没有排序过的元素 (15);
  • 找出插入提取元素的地方;和已经排序过的元素 20 比较;
  • 20 大于 15 成立,  则将现在已经排序过的元素20 向右移动1格;
  • 10 大于 15 不成立, 在现有位置上插入一个元素;
  • 提取第一个没有排序过的元素 (30);
  • 找出插入提取元素的地方;和已经排序过的元素 20 比较。
  • 20 大于 30 不成立, 在现有位置上插入一个元素;
  • 提取第一个没有排序过的元素 (12)。
  • ……..

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

2. 插入排序法全流程

走进开发,5分钟熟悉3种经典排序算法

3. 插入排序法总结

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

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

 

本文由 @动物园园长 原创发布。未经许可,禁止转载

题图来自 Pexels ,基于 CC0 协议

(0)
关键词:

运营大牛推荐