python 直接插入排序
Python 直接 插入排序
2023-09-27 14:25:29 时间
# 先将未排序的元素放到九天之上,一个临时变量temp,上到九天之上去观察前面已经排好的序列, # 然后从后向前对比,只要临时变量小于某个位置的值,就将其向前移动一位,就是给比它下标大 # 1的位置处赋值,它本身的值.这样它本身的位置空出来了.将九天之上的temp填入此处.直到
# 某个满足这样的条件才跳出循环,算一轮,1.遍历了前面所有的元素了,正常结束循环,算作一轮;2.遇到比temp小或等于的元素
# 此时,打断循环,算作一轮 def InsertSort(myList): length = len(myList) for i in range(1, length): temp = myList[i] for j in reversed(range(i)): if myList[j] > temp: myList[j + 1] = myList[j]
myList[j] = temp
else:
break
if __name__ == '__main__': myList = [12, 15, 9, 20, 6, 31, 24] InsertSort(myList) print(myList)
插入排序的主要思想是每次取一个列表元素与列表中已经排序好的列表段进行比较,然后插入从而得到新的排序好的列表段,最终获得排序好的列表。
比如,待排序列表为[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 中requests的返回数可直接使用json
- 别这样直接运行 Python 命令,否则电脑等于“裸奔”
- Python连接ActiveMQ的操作
- Python zip函数及用法
- 使用 Python 创建你自己的 Shell(下)
- gyp ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- 【python】+配置文件+操作yaml文件
- python实现散列表的直接寻址法
- python之模块contextlib 加强with语句而存在
- 【21天学习经典算法】直接选择排序(附Python完整代码)
- Nvidia GPU 入门教程之 08 如何在 Python 中使用 Kaggle API,直接从 Kaggle 快速下载数据集
- python字符串拼接N种姿势
- 《Python自动化运维:技术与最佳实践》一1.2 实用的IP地址处理模块IPy
- Python 值传递和引用传递
- PySpider python 爬虫
- 【Python爬虫】:Scrapy数据持久化
- 【图像处理】——Python+opencv实现提取图像的几何特征(面积、周长、细长度、区间占空比、重心、不变矩等)