上一节课我们已经讲了算法的基础知识,这节课我们讲一下算法中两个最为经典的类型:排序算法和查找算法。排序和查找我们之前直接使用列表的内置方法,那实现排序和查找最底层的原理是什么呢?我们正式开始这节课的内容吧。
一、排序算法1.1 冒泡排序冒泡排序是最简单的一种排序方法,它的原理是将一列数据中较大(或较小)的数据逐次向右推移的一种排序方法。冒泡排序分为内外两层循环。外层是总共要跑的遍数,2个数据比较一遍,3个数据比较一遍,以此类推,n个数据就跑了n-1遍。内层循环真正比较数据。以升序为例,每次比较把较大的放到后面。由于每一遍都是将本遍最大的数据移动到最右边。就像是水中的气泡一样,小的气泡上升,就排到最上面,就像是“冒泡”一样,所以我们称它为冒泡排序。
下面我们以升序为例,讲一下冒泡排序的基本思想:
第一遍从第1个元素开始,让它和第2个元素进行比较,如果大数在前就交换;然后让2个元素和第3个元素比较,大数在前就交换;依次类推,直到比较完最后一个元素为止。第一遍排序结束时,最后一个元素是所有元素中的最大值。
第二遍从第一个元素开始,让它和第2个元素进行比较,如果大数在前就交换;然后让2个元素和第3个元素比较,大数在前就交换;依次类推,直到比较到倒数第二个元素为止。第二遍排序结束时,倒数第二个数为第二大的数。
……
n个数排序共需要n-1遍。
我们看一下模拟的实例:
3 9 2 1 6 原始数据
3 9 2 1 6 将3和9比较,不交换位置
3 2 9 1 6 将9和2比较,交换位置
3 2 1 9 6 将1和9比较,交换位置
3 2 1 6 9 将9和6比较,交换位置。第一轮结束
2 3 1 4 9 将3和2比较,交换位置
2 1 3 4 9 将3和1比较,交换位置
2 1 3 4 9 将3和4比较,不交换位置。第二轮结束
……
下面我们看一下冒泡排序的Python代码实现:
a = [3, 9, 2, 1, 6]
count = len(a)
for i in range(0, count - 1): # 外层循环
for j in range(0, count -1 - i): # 内层循环
if a[j] > a[j 1]:
a[j], a[j 1] = a[j 1], a[j] # 两个数交换
print(a)
1.2 选择排序
选择排序对冒泡排序的改进。选择排序是在参加排序的所有元素中找出数值最小或最大的元素,如果它不是左侧第一个元素,就让它和左侧第一个元素交换位置;然后在余下的元素中找出数值最小或最大的元素,如果它不是左侧第二个元素,就与左侧第二个元素交换位置;……依次类推,直到所有元素构成有序的序列。
比起冒泡排序,选择排序更符合人们日常的排序习惯。它的比较次数与冒泡排序相通,但是交换的次数比冒泡排序要少,因此具有更高的效率。
下面我们以升序为例,讲一下选择排序的基本思想:
第一遍从第1个元素到第n个元素中找出一个最小的元素,如果它不是第1个元素,就让它和第1个元素交换位置。第一遍排序结束时,第1个元素为所有元素中的最小值。
第二遍从第2个元素到第n个元素中找出一个最小的元素,如果它不是第2个元素,就让它和第2个元素交换位置。第二遍排序结束时,第2个元素为所有元素中第二小的值。
……
下面我们看看如何实现最小元素的交换位置:
第i遍排序开始时,先假设第i个位置上的数是最小的数,用k标记。让k位置上的数(a[k])与i后面的数(a[j])逐个比较,当找到一个比k位置上小的数,用k记录j的值。当j到达最后一个数时,一遍比较结束,k指向最小的数,即k记录最小的数的位置。当i≠k时,交换a[i]与a[k]的值。
我们看一下选择排序的Python代码实现:
a = [3, 9, 2, 1, 6]
count = len(a)
for i in range(0, count - 1):
k = i
for j in range(i 1, count):
if a[k] > a[j]:
k = j
if k != i:
a[k], a[i] = a[i], a[k]
print(a)
1.3 插入排序
插入排序是先将待排序的数列中的第1个元素看成一个有序的子数列,然后从第2个元素开始,将数据逐个插入这个有序的子数列中,以此类推到最后一个数据。整个排序的过程类似于玩扑克牌时一边抓牌一遍理牌的过程,每抓一张牌就把它插入到应有的位置上。
插入排序的整个过程如下图所示:
插入排序
第1次插入,将第2个元素与第1个元素比较。先将要插入到数a[1]放入一个空的变量key;将key与前面已经排好序的元素比较,如果key<a[0]成立,说明key要插入到a[0]前面,将a[0]向后移动一个位置,放到a[1]中,再将key放到a[0]中;如果key<a[0]不成立,说明key要插入到a[0]后面,放key放入到a[1]的位置中。
第2次插入,前面两个元素已经排好序,将第3个元素放入一个空的变量key,将key与前面排好序的元素比较,再将它插入对应的位置中。
……
依次类推。
我们看一下插入排序的Python代码实现:
a = [3, 9, 2, 1, 6]
count = len(a)
for i in range(1, count):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j 1] = a[j]
j -= 1
a[j 1] = key
print(a)
1.4 其他排序算法
以上三种排序的算法外,还有归并排序、快速排序、堆排序、计数排序、桶排序、希尔排序等等,快速排序的思想下节课我们会讲解,归并排序这里就略去不讲了,大家可以自己研究。别的排序算法相对较为复杂,目前阶段不需要大家掌握。有兴趣的同学可查阅相关资料。
相对好理解一些的是归并排序(暂时不需要掌握代码),大家可以看动画的图片做相应的理解:
归并排序
二、查找算法2.1 顺序查找顺序查找是一种最为常用的查找算法。我们生活中也经常会用到,比如我们要从一堆书里面找到我们想要的书,我们会从第一本开始一本一本地看,直到找到我们想要的那本书。
顺序查找的基本思想是从第一个元素开始,按顺序逐个将数据与给定的数据进行比较,如果某个数据与给定的数据相等,则查找成功,输出所查数据;反之则未找到。
顺序查找的代码使用Python实现也非常简单:
data = [12, 23, 1, 89, 34, 13, 78, 67, 54]
key = 34 # 要查找的元素
x = -1 # 要查找元素的索引
count = len(data)
for i in range(0, count):
if data[i] == key:
x = i
break
if x == -1: # -1代表元素未找到
print('元素不存在')
else:
print(x)
2.2 对分查找
对分查找又称二分查找,是一种高效的查找方法。对分查找的前提是被查找的序列是有序的。
我们思考一个问题,从1到100中随机一个数字,猜出这个数是多少。如果我们从1开始一个个往后猜,每次只能排除一个数字,最坏的情况我们可能要猜100次。但是如果第一次猜50,告诉你大了或者小了。下次再猜25,再下次猜12,以此类推,不管是哪个数字,最多7次之内就能猜出来了。这样比起顺序查找要省了很多的时间。这就是对分查找算法。
我们看看对分查找的思路:
如果key是我们需要查找的值,列表a中存放了n个已经升序排列的元素,m为查找范围[i, j]的中间位置。我们查找的过程中必然是以下三种情况之一:
- 如果key < a[m],key在前半部分,新的查找范围在[i, m-1]中
- 如果key = a[m],找到需要对数据
- 如果key > a[m],key在后半部分,新的查找范围在[m 1, j]中
我们看一下对分查找的Python代码实现:
data = [2, 34, 36, 47, 51, 53, 59, 62, 75, 79, 82]
key = 47 # 需要查找的元素
count = len(data)
i, j = 0, count - 1
x = -1
while i <= j:
m = (i j) // 2
if key == data[m]:
x = m
break
elif key > data[m]:
i = m 1
else:
j = m - 1
if x == -1:
print('未找到元素')
else:
print(x)
三、课后思考题
1、选择题
列表l = [9, 2, 8, 6, 3, 4],采用选择排序进行升序排序,第二遍排序之后的结果是()
A. [2, 3, 8, 6, 9, 4]
B. [2, 8, 6, 3, 4, 9]
C. [2, 6, 3, 4, 8, 9]
D. [2, 3, 4, 6, 8, 9]
2、选择题
列表l = [5, 2, 6, 3, 7],利用插入排序进行升序排序,第二次插入排序的结果是()
A. [5, 2, 3, 6, 7]
B. [2, 5, 3, 6, 7]
C. [2, 5, 6, 3, 7]
D. [2, 3, 5, 6, 7]
3、选择题
某个列表中有7个元素,依次为19、28、30、35、39、42、48。如果采用对分查找法在列表中查找元素48,需要查找的次数是()
A. 1 B. 2 C. 3 D. 4
四、上节课思考题答案1、C
2、C
3、参考代码
n = 0 # 统计个数
for i in range(100, 1000):
a = i // 100 # 百位数
b = i % 100 // 10 # 十位数
c = i % 10 # 个位数
if a ** 3 b ** 3 c ** 3 == i:
n = 1
print(i)
print("合计个数:", n)
,
〖特别声明〗:本文内容仅供参考,不做权威认证,如若验证其真实性,请咨询相关权威专业人士。如有侵犯您的原创版权或者图片、等版权权利请告知 wzz#tom.com,我们将尽快删除相关内容。