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

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

内容简介:【 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)


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

查看所有标签

猜你喜欢:

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

Java语言程序设计

Java语言程序设计

(美) Y. Daniel Liang / 李娜 / 机械工业出版社 / 2011-6 / 79.00元

本书是Java语言的经典教材,畅销多年不衰。本书全面整合了Java的特性,采用“先讲基础”的教学方式,循序渐进地介绍了程序设计基础、面向对象程序设计、GUI程序设计等。另外,本书还全面且深入地覆盖了一些高级主题,包括算法和数据结构、并发、网络、国际化、高级GUI、数据库和Web程序设计等。 本书中文版由《Java语言程序设计 基础篇》和《Java语言程序设计 进阶篇》组成。基础篇对应原书的第......一起来看看 《Java语言程序设计》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具