算法学习笔记(一):插入排序和线性查找

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

新老客户大回馈,云服务器低至5折

(一)插入排序

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

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Python数据分析开发环境

下一篇:python3:操作excel文件