排序算法之插入排序的python实现
2024-09-05 15:56:51
插入排序的工作原理如下:
(1)从数组第一个元素开始(0下标),从该元素开始进行构建有序序列;
(2)取出待排序列中第一个元素,然后从“有序”序列中,从后往前扫描;
(3)如果该元素(有序序列)大于待插入元素(待排序列),将该元素后移一个位置;
(4)重复步骤3,直到找到“有序序列”中某一元素小于或等于“待插入元素”的位置;
(5)将待插入元素插入到该元素(有序序列)后面(i+1)的位置上;
(6)重复步骤2~5,直到待排序列中没有元素。
例子实现步骤图:
最优时间复杂度:O(n)
最坏时间复杂度:O(n²)
稳定性:稳定
优点:稳定,比较快
缺点:比较次数不确定,数据量越大,该算法越差
#!/usr/bin/env python
# -*- coding:utf-8 -*-
__author__ = "hsz" def insert_sort(alist):
"""
插入排序
index:有序序列尾元素下标
value:有序序列尾元素值
:param alist: 待排序列
:return:
"""
n = len(alist)
for i in range(1, n):
index = i - 1
value = alist[i] while index >= 0 and alist[index] > value:
# 将待插入元素依次与有序序列比较(从右至左),
# 直到找到有序序列中某一元素小于待插入元素或者没有找到比待插入元素小的值;
alist[index + 1] = alist[index]
index -= 1 # 将待插入的元素,插入到有序系列中:
# 若找到有序序列中某一个元素小于待插入元素,则将待插入元素插入到该元素后面;
# 若在有序序列中没有找到大于待插入元素的值,则将待插入元素位置不变;
alist[index + 1] = value if __name__ == "__main__":
li = [53, 27, 36, 15, 69,42]
print("排序前的列表", li)
insert_sort(li)
print("排序后的列表", li)
最新文章
- STL 内存释放
- Java web MVC开发模式入门感悟
- HTML5——语音输入
- iOS开发拓展篇—音乐的播放
- Google Code Jam 2010 Round 1B Problem B. Picking Up Chicks
- [CSS]三角形
- 你认为A和B所在方格颜色相同吗?
- JavaScript效果之选项卡
- id有空格获取不到元素
- codesmith的使用
- Qt编程之Qt样例表(QSS)
- 图片翻页效果引出的animate.css,很好玩,多动动吧~
- 一致性哈希算法(consistent hashing)样例+測试。
- Ambari安装之Ambari安装前准备(CentOS6.5)(一)
- x&;(x-1)
- react连连看
- Java: 在dos窗口输入密码,不要把密码直接显示出来,原来可以这么简单
- java多线程快速入门(一)
- Swift 中函数使用指南
- poj 2253 一条路径中的最大边 再找出最小的