【 python 学习笔记 -- 数据结构与算法 】插入排序 Insertion Sort

栏目: Python · 发布时间: 8年前

内容简介:【 python 学习笔记 -- 数据结构与算法 】插入排序 Insertion Sort

【插入排序】:每次保证列表最左端子序列是排好顺序的,然后取下一个元素,扫描其左端的子序列,将其中大于目标元素的元素右移一个位置,直到找到合适的位置将目标元素插入子序列中。逐步增大 排序 完成的sublist的长度,最终完成整个列表的排序

算法思路如下:

1. 列表最左边第一个元素认为已经排序好了

2. 取下一个元素(目标元素),在它前面已经排序完成的子序列中从后向前扫描

3. 如果子序列中被扫描的当前元素大于目标元素,则将当前元素右移一个位置

4. 重复第3步,直到被扫描的元素小于或等于目标元素

5. 将目标元素插入到步骤4中所述元素的右面

6. 重复上述2-5的步骤,直到列表最后一个元素插入到适当的位置,整个列表排序完成。

【 示意图 】

下图是完成插入排序的整个过程

【 python 学习笔记 -- 数据结构与算法 】插入排序 Insertion Sort

下图是灰色部分是已经排好顺序的子列表。现在要插入下一个目标元素31,从子列表最右端元素开始扫描:

93>31,右移一个位置;77, 54 同理;26<31,把31插入26后面的位置。

【 python 学习笔记 -- 数据结构与算法 】插入排序 Insertion Sort

【 implementation of insertion sort】

【 python 学习笔记 -- 数据结构与算法 】插入排序 Insertion Sort

【 performance analysis 】

最坏的情况下,列表降序排列,比较次数为O(n 2 );最好的情况下,列表正序排列,比较次数为O(n)


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

How to Build a Billion Dollar App

How to Build a Billion Dollar App

George Berkowski / Little, Brown Book Group / 2015-4-1 / USD 24.95

Apps have changed the way we communicate, shop, play, interact and travel and their phenomenal popularity has presented possibly the biggest business opportunity in history. In How to Build a Billi......一起来看看 《How to Build a Billion Dollar App》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换