8月阅读周·秒懂算法:用常识解读数据结构与算法:算法优化,根据情况进行优化

举报
叶一一 发表于 2024/08/26 14:10:31 2024/08/26
【摘要】 背景去年下半年,我在微信书架里加入了许多技术书籍,各种类别的都有,断断续续的读了一部分。没有计划的阅读,收效甚微。新年伊始,我准备尝试一下其他方式,比如阅读周。每月抽出1~2个非连续周,完整阅读一本书籍。这个“玩法”虽然常见且板正,但是有效,已经坚持阅读七个月。已读完书籍:《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript(上卷)》、《你不知道的JavaScri...

背景

去年下半年,我在微信书架里加入了许多技术书籍,各种类别的都有,断断续续的读了一部分。

没有计划的阅读,收效甚微。

新年伊始,我准备尝试一下其他方式,比如阅读周。每月抽出1~2个非连续周,完整阅读一本书籍。

这个“玩法”虽然常见且板正,但是有效,已经坚持阅读七个月。

已读完书籍《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript(上卷)》、《你不知道的JavaScript(中卷)》、《你不知道的JavaScript(下卷)》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构:从入门到微前端》

当前阅读周书籍《秒懂算法:用常识解读数据结构与算法》

根据情况进行优化

插入排序

插入排序步骤如下:

(1) 在第一次遍历中,暂时移除索引1处(第二个格子)的值,把它存储在一个临时变量中。这样数组中就会有一个空位,在后续遍历中,还会移除其他索引处的值。

(2) 在移位阶段中,把空位左边的每个值和临时变量中存储的值进行比较,如果某个值大于临时变量,就把那个值右移。因为右移了值,所以空位自然就移动到了左边。如果遇到一个比临时移除的值更小的值,或者到达了数组的下界,那么移位阶段就结束了。

(3) 随后把临时移除的值插入空位。

(4) 第(1)~(3)步正是一次遍历的过程。不断重复遍历,直到某次遍历开始于数组的最后一个索引,那就意味着数组已经正确排序了。

插入排序实战

下面以数组[4, 2, 7, 1, 3]为例来详细介绍插入排序。

第一次遍历开始时,检查索引1处的值,也就是本例中的2。

第1步:暂时移除2,把它存储在名为temp_value的变量中。下图中用把这个值上移来表示移除。

第2步:比较4和temp_value,也就是2。

第3步:因为4大于2,所以把4右移。因为空位目前位于数组的下界,所以不再有可以右移的数。

第4步:把temp_value插入空位,从而结束第一次遍历。

接下来,开始第二次遍历。

第5步:在第二次遍历中,暂时移除索引2处的值并存储在temp_value中。因此temp_value的值现在是7。

第6步:比较4和temp_value。因为4更小,所以不移动它。因为我们遇到了一个比temp_value小的值,所以移位阶段就结束了。

第7步:把temp_value插入空位,从而结束第二次遍历。

接下来开始第三次遍历。

第8步:暂时移除1,存储到temp_value中。

第9步:比较7和temp_value。

第10步:因为7大于1,所以把7右移。

第11步:比较4和temp_value。

第12步:因为4大于1,所以把4右移。

第13步:比较2和temp_value。

第14步:因为2大于1,所以把2右移。

第15步:因为空位现在位于数组下界,所以把temp_value插入空位,从而结束这次遍历。

接下来开始第四次遍历。

第16步:暂时移除索引4处的值3,存储在temp_value中。

第17步:比较7和temp_value。

第18步:因为7大于3,所以把7右移。

第19步:比较4和temp_value。

第20步:因为4大于3,所以把4右移。

第21步:比较2和temp_value。因为2小于3,所以移位阶段结束。

第22步:把temp_value插入空位。数组到这一步已经排列正确。

代码实现:插入排序

def insertion_sort(array):
  for index in range(1, len(array)):
    temp_value = array[index]
    position = index - 1
    while position >= 0:
      if array[position] > temp_value:
        array[position + 1] = array[position]
        position = position - 1
    else:
      break
  array[position + 1] = temp_value
return array

插入排序的效率

插入排序中有4类步骤:比较、移位、移除和插入。要分析插入排序的效率,需要把它们都考虑进来。

首先来看比较。我们需要把空位左边的值和temp_value进行比较。在原数组倒序排列的最坏情况下,在每次遍历中,都需要把temp_value左边所有的值和temp_value进行比较。因为那些值全都比temp_value大,所以只有空位移动到数组左边界时才能停止遍历。

总共需要1 + 2 + 3 + … + (N -1)次比较。对有N个元素的数组来说,大约需要N^2 / 2次比较。

把一个值右移一个格子时需要移位。如果数组倒序排列,那么因为每次比较都需要右移,所以移位的次数和比较的次数是相同的。

在最坏情况下,插入排序的时间复杂度和冒泡排序以及选择排序相同,都是O(N^2)。

总结

辨别最好、平均和最坏情况是选择合适算法以及优化已有算法速度的重要技巧。记住:为最坏情况做打算当然是好事,但大多数时候出现的还是平均情况。


作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者,刑侦、无限流小说初级玩家。
如果看完文章有所收获,欢迎点赞👍 | 收藏️ | 留言📝

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。