8月阅读周·秒懂算法:用常识解读数据结构与算法:算法优化,根据情况进行优化
【摘要】 背景去年下半年,我在微信书架里加入了许多技术书籍,各种类别的都有,断断续续的读了一部分。没有计划的阅读,收效甚微。新年伊始,我准备尝试一下其他方式,比如阅读周。每月抽出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)