Python排序算法之直接插入排序
2024-10-18 08:20:33
插入排序的主要思想是每次取一个列表元素与列表中已经排序好的列表段进行比较,然后插入从而得到新的排序好的列表段,最终获得排序好的列表。
比如,待排序列表为[49,38,65,97,76,13,27,49],则比较的步骤和得到的新列表如下:
(带有背景颜色的列表段是已经排序好的,红色背景标记的是执行插入并且进行过交换的元素)
时间复杂度:O(n^2)
待排序: [49,38,65,97,76,13,27,49]
第一次比较后: [38,49,65,97,76,13,27,49] 第二个元素(38)与之前的元素进行比较,发现38较小,进行交换
第二次比较后: [38,49,65,97,76,13,27,49] 第三个元素(65)大于前一个元素(49),所以不进行交换操作,直接到下一个元素比较
第三次比较后: [38,49,65,97,76,13,27,49] 和第二次比较类似
第四次比较后: [38,49,65,76,97,13,27,49] 当前元素(76)比前一元素(97)小,(97)后移,(76)继续与(65)比较,发现当前元素比较大,执行插入
第五次比较后: [13,38,49,65,76,97,27,49]
第六次比较后: [13,27,38,49,65,76,97,49]
第七次比较后: [13,27,38,49,49,65,76,97]
从百度百科上盗了一张图:
Python实现代码如下:
# Coded by Alvin def InsertSort(myList):
#获取列表长度
length = len(myList) for i in range(1,length):
#设置当前值前一个元素的标识
j = i - 1 #如果当前值小于前一个元素,则将当前值作为一个临时变量存储,将前一个元素后移一位
if(myList[i] < myList[j]):
temp = myList[i]
myList[i] = myList[j] #继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素
j = j-1
while j>=0 and myList[j] > temp:
myList[j+1] = myList[j]
j = j-1 #将临时变量赋值给合适位置
myList[j+1] = temp myList = [49,38,65,97,76,13,27,49]
InsertSort(myList)
print(myList)
运行结果:
最新文章
- Java排序算法——基数排序
- 腾讯云TCCE培训认证 精彩的第一次
- [POI2008]KLO &;&; POC
- C# 轻量级ORM 编写思维
- 【CISP笔记】安全漏洞与恶意代码(1)
- 优化listview列表速度
- Codeforces 706 C. Hard problem (dp)
- Java基础之String,StringBuilder,StringBuffer
- Android WebView Error – Uncaught TypeError: Cannot call method ‘getItem’ of null at
- linux 下编译安装php
- 2015 ACM / ICPC 亚洲区域赛总结(长春站&;北京站)
- 用Hyperledger Fabric(超级账本)来构建Java语言开发区块链的环境
- 运行SSIS包的六种方式
- CTS问题分析6
- jsp的page、request、session、application四个作用域的作用
- 理解OpenShift(1):网络之 Router 和 Route
- kbmMW 5.08.10试用报告
- kvm 创建新虚拟机命virt-install 使用说明
- jQuery动画animate方法使用介绍
- kill word out e ef en em
热门文章
- Struts1简单开发流程梳理
- “四则运算生成程序——GUI支持和部分功能改进”链接
- 使用robot封装一个模拟键盘复制粘贴并按下回车的方法
- [转帖] 中国SaaS死或生之二: ERP两大邪术,尽出歪门邪路 ---- 挺好玩的
- Android 目录结构
- 深入探索.NET内部了解CLR如何创建运行时对象
- 解决还原数据库是出现system.data.sqlclient.sqlerror filestream功能被禁用的问题
- LINQ to SQL和Entity Framework
- QML——添加自定义模块
- P4071 [SDOI2016]排列计数