算法学习笔记（一）：插入排序和线性查找
（一）插入排序
看下面这张图片：把打牌时手上的牌抽象为一个列表A，j表示当前最新抓的牌的索引（先放到手上最右边）
索引 j =0 时 A[j] = 3
j >= 1时，
1、我们拿到第2张牌时，我们会把 7和3比较一下(3<7)，然后放到3的后面
（此时 A[0] = 3 A[1] = 7）
2、拿到第3张牌时 ，我们会把 1从右到左和前面的牌比较（1<7,1<3），然后插入到3的前面。
（此时 A[0] = 1 A[1] = 3 A[2] = 7）
3、转换为代码逻辑，大概意思就是（A[j]代表当前抓的牌。下面假设先把抓的牌放到手上最右边（右1就是手上最新抓的牌），然后再去调整位置，就和上图中的1一样）
key = A[j] #当前抓的牌（右1）
i = j – 1 #获取前一牌的索引（右2）
while key < A[i]: #如果当前抓的牌小于前一张牌（从右到左依次比较）
A[i+1] = A[i] #把前一张牌往右移一个位置
i = i – 1 #继续获取更前一张牌的索引（第一次运行 是 右3的索引，第二次是右4的索引。。。）
A[i+1] = key #key >=A[i] 时，将当前抓的牌插入到A[i]的后面（就像上面把7插到5的后面一样)
比喻可能不是非常恰当，不过大概是这样的意思。
实现代码：
1 import numpy as np
2
3 #创建一个ndarray对象
4 A = np.array([5,2,4,7,6,10,1,3,9])
5
6 #升序排序版本
7 for j in range(len(A)):
8 key = A[j]
9 i = j - 1
10 while i >= 0 and key < A[i]:
11 A[i+1] = A[i]
12 i = i-1
13 A[i+1] = key
14
15 print(A)
16 #降序排序版本
17 for j in range(len(A)):
18 key = A[j]
19 i = j - 1
20 while i >= 0 and key > A[i]:
21 A[i+1] = A[i]
22 i = i -1
23 A[i+1] = key
24
25 print(A)（二）线性查找
1 import numpy as np
2
3 #找到结果，返回索引，否则返回None
4 def search(array,key):
5 for j in range(len(array)):
6 if array[j] == key:
7 return j
8 return None
9
10 array = np.array([5,2,4,7,6,10,1,3,9])
11 key = 10
12
13 print(search(array,key))本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-05-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读