首页 > > 网络编程 > 其它 >

算法学习笔记（一）：插入排序和线性查找

2018-06-18 03:02:00来源：未知阅读 ()

（一）插入排序

看下面这张图片：把打牌时手上的牌抽象为一个列表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))