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

(一)插入排序

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏aoho求索

由散列表到BitMap的概念与应用(三):海量数据处理

遍历文件a,对每个url求取hash(url)%1000,然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,…,a999,每个小文件约300...

15810
来自专栏极客猴

Python 中连接字符串效率最高的方式是哪种呢?

在编码过程中,我们经常需要对字符串进行连接处理操作。如果我们能使用优雅的方式来处理字符串连接,那么程序内存开销会小很多。

11120
来自专栏老马说编程

计算机程序的思维逻辑 (9) - 强大的循环

循环 上节我们介绍了流程控制中的条件执行,根据具体条件不同执行不同操作。本节我们介绍流程控制中的循环,所谓循环就是多次重复执行某些类似的操作,这个操作一般不是...

22180
来自专栏小李刀刀的专栏

[译]Laravel 5.0 之 Eloquent 属性转换

本文译自 Matt Stauffer 的系列文章. ---- 之前完全忘了要把这个 Laravel 5 的系列博客写完,不过最近看到了一篇关于属性转换的简介 L...

44380
来自专栏林冠宏的技术文章

经典面试问题: Top K 之 ---- 海量数据找出现次数最多或,不重复的。

作者:林冠宏 / 指尖下的幽灵 掘金:https://juejin.im/user/587f0dfe128fe100570ce2d8 博客:htt...

728150
来自专栏take time, save time

你所能用到的数据结构(九)

十二、为了count的最终胜利 在介绍完最基本的堆栈模型之后,下面要继续的是第二种最基本的模型,队列。队列,在现实生活中经常可以看到(不过考虑到在我国大部分人...

29570
来自专栏灯塔大数据

技术 | Python从零开始系列连载(十九)

但它的特点就是下次使用next(a)时,接着上次的断点继续运行,直到下一个yield

11930
来自专栏用户2442861的专栏

近一个月的面试总结 分类:JAVA

本文转载自:http://blog.csdn.net/pistolove/article/details/46753275

14220
来自专栏老九学堂

1分钟彻底理解C语言指针的概念

计算机中所有的数据都必须放在内存中,不同类型的数据占用的字节数不一样,例如 int 占用4个字节,char 占用1个字节。为了正确地访问这些数据,必须为每个字节...

53580
来自专栏

shell之sort命令

1 sort的工作原理 sort将文件的每一行作为一个单位,相互比较,比较原则是从首字符向后,依次按ASCII码值进行比较,最后将他们按升序输出。 [rocro...

21670

扫码关注云+社区

领取腾讯云代金券