python算法与数据结构-插入排序算法
程序员文章站
2022-07-08 13:22:16
...
插入排序分析
开始的默认的第一个元素93为有序系列,其余的元素为无序系列,如下所示:
54和93比,54比93小,所以把54放在前面,如下所示:
代码如下所示:
# coding:utf-8
def insert_sort(alist):
"""插入排序"""
n = len(alist)
#从右边的无序序列中取出多少个元素执行这样的过程
for j in range(1,n):
# j = [1,2,3,n-1]
#i 代表内层循环起始值
i = j
#执行从右边的无序序列中取出第一个元素,即i位置的元素,然后将其插入到前面的正确位置中
while i>0: #i = [1,2,3,4,5,6] 内层循环i的范围就是i从1到n-1
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i-=1
else: #最优时间复杂度就是已经排好序的情况,也就是O(n)
break
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
insert_sort(li)
print(li)
"""
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
"""
另外一种写法如下所示:
def insert_sort(alist): # 获取需要排序数据的个数 n = len(alist) # 插入排序的第一次插入从第二个数字开始选择,所以下标从1开始 for j in range(1,n): # 从选择插入的数据,一次和它前一个比较,主要比前面的小就交换 for i in range(j,0,-1): # 实际是这样的,range(10, 0, -1) # 意思是从列表的下标为10的元素开始,倒序取到下标为0的元素(但是不包括下标为0元素),也就是说list[10] - list[1], 转化成range就是相当于range(1, 11) # 的倒序, 最后得到的结果是[10,9,8,7,6,5,4,3,2,1] if alist[i]<alist[i-1]: temp = alist[i] alist[i] = alist[i-1] alist[i-1] = temp if __name__ == "__main__": li = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(li) insert_sort(li) print(li)
上一篇: JAVA数据类型转换
下一篇: shell排序