Python实现插入排序（用python进行排序）

off999 2024-10-27 11:50 26 浏览 0 评论

'''
插入排序原理：将待排序序列的第一个元素当做已排序序列，其他的元素当做未排序序列，取未排序的第一个元素与已排序的最后一个元素进行比较，
如果未排序的第一个元素小于已排序的最后一个元素则交换位置，交换位置后继续与前一个相邻位置的元素进行比较，当不需要交换时，则次轮插入完成。
继续循环上面步骤，每进行一轮插入，已排序的序列加1，未排序的序列减1，一直到列表中的元素全部被插入到已排序的序列中为止，插入排序完毕。
例如数组：{38,65,97,76,13,27,49}，具体排序过程如下：
第1轮插入38以后：[38] 65 97 76 13 27 49
第2轮插入65以后：[38 65] 97 76 13 27 49
第3轮插入97以后：[38 65 97] 76 13 27 49
第4轮插入76以后：[38 65 76 97] 13 27 49
第5轮插入13以后：[13 38 65 76 97] 27 49
第6轮插入27以后：[13 27 38 65 76 97] 49
第7轮插入49以后：[13 27 38 49 65 76 97]
'''
#实现代码
def insert_sort(arrays):
    count=len(arrays)
    for i in range(count):
        key=arrays[i]
        j=i-1
        while j>=0 and key<arrays[j]:
            arrays[j+1]=arrays[j]
            arrays[j]=key
            j-=1
    return arrays

if __name__ == '__main__':
    arrays = [38, 65, 97, 76, 13, 27, 49]
    print("排序前：" + str(arrays))
    print("排序后：" + str(insert_sort(arrays)))

看一下执行结果：

时间复杂度：

插入排序中每一轮插入都需要移动到最左端,需要进行 n-1 轮"插入",每一轮"插入"需要向前比较和移动 i 次,i 的平均值为 n/2, 时间复杂度为 T(n)=n(n-1)/2,再乘每次操作的步骤数,所以插入排序的时间复杂度为: O(n2)

空间复杂度：O(1)

欢迎大家关注我的微信公众号

python快速排序

上一篇：学好了python，我们可以实现排序算法了
下一篇：Python实战课程-搭建学生信息管理系统(六)排序(升序、降序)

Python实现插入排序（用python进行排序）

相关推荐

取消回复欢迎你发表评论:

抖音上好看的小姐姐，Python给你都下载了

全网最简单易懂!495页Python漫画教程，高清PDF版免费下载

编写一个自动生成双色球号码的 Python 小脚本

Python基础编程——赋值语句的高级用法

python入门到脱坑输入与输出—str()函数

推荐一款好用的国产桌面软件开发工具Aardio

Python基础之元组、集合、字典

python之容器详解——字典

Python启航:30天编程速成之旅(第12天)- 类

python 解决cv2绘制中文乱码问题

Python实现插入排序（用python进行排序）

相关推荐

取消回复欢迎 你 发表评论:

抖音上好看的小姐姐，Python给你都下载了

全网最简单易懂!495页Python漫画教程，高清PDF版免费下载

编写一个自动生成双色球号码的 Python 小脚本

Python基础编程——赋值语句的高级用法

python入门到脱坑 输入与输出—str()函数

推荐一款好用的国产桌面软件开发工具Aardio

Python基础之元组、集合、字典

python之容器详解——字典

Python启航:30天编程速成之旅(第12天)- 类

python 解决cv2绘制中文乱码问题

取消回复欢迎你发表评论:

python入门到脱坑输入与输出—str()函数