直接插入排序--循环实现

142 阅读 0 评论 94 点赞

我是靠谱客的博主成就中心，这篇文章主要介绍直接插入排序--循环实现，现在分享给大家，希望可以做个参考。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 1 # 版本1 自己写的 ，效率有点低
 2 
 3 %%timeit # 2.92 µs ± 62.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
 4 lst = [1,5,7,6]
 5 newlst = [0] + lst # [0,1,9,8,5,6]
 6 
 7 
 8 for i in range(2, len(newlst)):# 2,   3,   4, 5
 9     newlst[0] = newlst[i] # 9,   8,   5, 6
10     for j in range(i-1,0,-1):# 1,   2 ,1,    3,2,1,  4,3,2,1
11         if newlst[0] < newlst[j]:# 
12             newlst[j+1] = newlst[j]
13         if newlst[0] > newlst[j]:
14             newlst[j+1] = newlst[0]
15             break
16 #     print(newlst)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 1 # 第二版本
 2 
 3 %%timeit # 1.48 µs ± 23.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
 4 lst = [1,5,7,6]
 5 newlst = [0] + lst # [0,1,9,8,5,6]
 6 
 7 for i in range(2, len(newlst)):
 8     newlst[0] = newlst[i]
 9     
10     j = i - 1
11     if newlst[j] > newlst[0]:
12         while newlst[j] > newlst[0]:
13             newlst[j+1] = newlst[j]
14             j -= 1
15         newlst[j + 1] = newlst[0]
16 # print(newlst)
17         
18         
19         
20

直接插入排序：

　　直接插入排序原理：

　　　　在未排序的序列中，构建一个子排序序列，直至全部数据排序完成

　　　　将待排序的数，插入到已经派苏的序列中合适的位置

　　　　增加一个哨兵位置，用来放入待比较值，让他和后面已经排好序的序列比较，找到合适的插入点

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 1 lst = [1,4,9,8,6]
 2 
 3 
 4 '''
 5     [5,3,1,2]--[3,5,1,2] --[1,3,5,2] -- [1,2,3,5]
 6 '''
 7 length = len(lst) # 4
 8 
 9 for i in range(1, length): # [1,3] 1,2
10     min = lst[:i] # [5] ,[3,5]
11     for j in range(len(min)): # 0    0,1
12         if lst[i -j] < min[len(min) -1 -j]: # 3 <5    1<5
13             lst[i-j], lst[len(min) -1-j] = lst[len(min)-1-j],lst[i-j] #
14             # print('--')
15 print(lst)