python简单的实现插入排序和二分插入排序

零：环境

Python 3.6.5

JetBrains PyCharm 2018.1.4 x64

一：正常的插入排序

　　插入排序如字面意思，是将数据一个一个的插入到列表里以形成有序数列

　　插入排序的前提是被插入的序列是有序的，我们可以将空序列或者一个元素的序列视为有序序列

　　然后每次都取一个新的元素去和有序序列里的元素进行遍历比较，当找到第一个比它大的数时，就insert到那个位置，到结尾就是插入到结尾

　　因为是有序的所以找到的地方就是正确的地方，在那和之后的位置都比要插入的数要大

　　比如说有这样一个数组

v_数组 = [126,2,4,56,65,45,78,32,96,1]

　　我们假设一开始有一个空数组r_数组 = []

　　我们遍历v_数组，将每个数都试图插入到r_数组内

　　1:第一步

　　v_插入元素下标 = 0

　　插入的元素即为v_数组[v_插入元素下标]

　　v_下标 = 0

　　v_下标 用来遍历r_数组来寻找第一个比要插入元素大的位置。

　　在这里我们遍历的时候由于v_下标到达了len(r_数组)，所以我们将第一个元素插入到r_数组里

　　r_数组即为: [126]

　　2:第二步

　　v_插入元素下标 += 1

　　v_下标重置为0

　　要插入的元素为第二个元素即2

　　遍历的时候发现第一个元素就比2大，所以我们insert到r_数组里的第0位

　　r_数组即为[2,126]

　　2:第三步

　　v_插入元素下标 += 1

　　v_下标重置为0

　　要插入的元素为第三个元素即4

　　遍历的时候发现第二个元素128，即下标为1时，才大于4，所以我们insert到r_数组里的下标1处

　　r_数组即为[2,126]

　　4:以此类推……

　　当v_数组遍历完毕之后r_数组就是有序的了

　　以下是参考代码

1 def f_插入排序(p_数组):
2     r_数组 = []
3     for t_下标 in range(len(p_数组)):
4         v_插入位置 = 0
5         while v_插入位置 < len(r_数组) and r_数组[v_插入位置] < p_数组[t_下标]:
6             v_插入位置+=1
7         r_数组.insert(v_插入位置,p_数组[t_下标])
8     return r_数组

二：二分插入排序

　　在我们明白了插入排序之后，二分插入排序也就很简单了

　　二分插入排序实际上就是是二分查找+插入排序

　　二分查找类似于我们数学上所学过的二分法找根元素

　　因为插入排序所特有的特性，我们在查找第一个比插入元素key大的元素的时候，我们可以从中间先开始找，如果中间元素比key还小，那么就说明要插入的位置肯定在中间的右侧部分段

　　反之就是必定在中间的左侧部分段

　　然后我们再把左侧或右侧元素视为一个单独的序列，然后再这个序列里再次二分查找，很容易可以想到这样到最后就会得到正确的位置

　　以下是参考代码

 1 #   二分插入排序
 2 def f_算法5_1():
 3     s = [126,1]
 4     rs=[]
 5     for it in s:
 6         #   右值可能越界，但是(l + r) // 2一定不会越界
 7         l,r = 0,len(rs)
 8         #   当插入位置到达边界或大于边界时说明结束
 9         while l < r:
10             #   当目标值大于中值时，目标值肯定至少插在中值后一个
11             if it > rs[(l + r) // 2]:
12                 l = (l + r) // 2 + 1
13             #   当目标值小于等于中值时，目标值的上界至少为中值
14             else:
15                 r = (l + r) // 2
16         #   初始没有时就插在0处
17         rs.insert(l,it)
18         pass
19     print(rs)
20     pass

?

　　以上皆为自己所学所思，转载请注明出处