黑马程序员技术交流社区
标题:
【上海校区】python（五.5.4、插入排序(Insert)）
[打印本页]
作者:
不二晨
时间:
2019-2-19 10:26
标题:
【上海校区】python（五.5.4、插入排序(Insert)）
文章目录
效率：O(n2)
原理：
以从小到大排序为例，元素0为第一个元素，插入排序是从元素1开始，尽可能插到前面。
插入时分插入位置和试探位置，元素i的初始插入位置为i，试探位置为i-1，在插入元素i时，依次与i-1,i-2······元素比较，如果被试探位置的元素比插入元素大，那么被试探元素后移一位，元素i插入位置前移1位，直到被试探元素小于插入元素或者插入元素位于第一位。
重复上述步骤，最后完成排序
demo：
def insert_sort(data):
"""
插入排序
:param data: 待排序的数据列表
:return:
"""
for i in range(1, len(data)): # 无序区域数据
tmp = data
# 第i次插入的基准数
for j in range(i, -1, -1):
if tmp < data[j - 1]: # j为当前位置，试探j-1位置
data[j] = data[j - 1] # 移动当前位置
else: # 位置确定为j
break
data[j] = tmp # 将当前位置数还原
if __name__=='__main__':
import random
data_list=list(range(30))
random.shuffle(data_list) # 打乱列表数据
print("pre:",data_list)
insert_sort(data_list)
print("after:",data_list)
#结果：
#pre: [7, 17, 10, 16, 23, 24, 13, 11, 2, 5, 15, 29, 27, 18, 4, 19, 1, 9, 3, 21, 0, 14, 12, 25, 22, 28, 20, 6, 26, 8]
#after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
---------------------
【转载，仅作分享，侵删】
作者：Mr Cui
原文：
https://blog.csdn.net/cui130/article/details/86499879
版权声明：本文为博主原创文章，转载请附上博文链接！
作者:
不二晨
时间:
2019-2-20 09:32
今天也要加油鸭
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2
今天也要加油鸭