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 %%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 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)
直接插入排序：
最好情况，正好是升序排列，比较迭代 n-1 次
最差的情况，正好是降序排列，比较迭代1,2,3,4，...，n-1即n(n-1)/2
使用两层嵌套循环，时间复杂度O（n^2）
稳定排序算法：
如：3,2,2,1 排序后，1,2,2,3 中间的2,2 前后顺序是不变的，所以称为稳定排序
使用在小规模数据比较
可优化点：
如果比较操作耗时大的话，可以采用二分查找来提高效率，即二分查找插入排序。最最要的是每次找到数据要插入的位置后，后面的数字要往后挪，是需要很大的时间的。