青少年Python编程系列36:排序算法和查找算法入门

青少年Python编程系列36:排序算法和查找算法入门上一节课我们已经讲了算法的基础知识,这节课我们讲一下算法中两个最为经典的类型:排序算法和查找算法。我们看一下模拟的实例:3 9 2 1 6 原始

欢迎大家来到IT世界,在知识的湖畔探索吧!

上一节课我们已经讲了算法的基础知识,这节课我们讲一下算法中两个最为经典的类型:排序算法和查找算法。排序和查找我们之前直接使用列表的内置方法,那实现排序和查找最底层的原理是什么呢?我们正式开始这节课的内容吧。

一、排序算法

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) 

欢迎大家来到IT世界,在知识的湖畔探索吧!

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代码实现:

欢迎大家来到IT世界,在知识的湖畔探索吧!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个元素开始,将数据逐个插入这个有序的子数列中,以此类推到最后一个数据。整个排序的过程类似于玩扑克牌时一边抓牌一遍理牌的过程,每抓一张牌就把它插入到应有的位置上。

插入排序的整个过程如下图所示:

青少年Python编程系列36:排序算法和查找算法入门

插入排序

第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 其他排序算法

以上三种排序的算法外,还有归并排序快速排序、堆排序、计数排序、桶排序、希尔排序等等,快速排序的思想下节课我们会讲解,归并排序这里就略去不讲了,大家可以自己研究。别的排序算法相对较为复杂,目前阶段不需要大家掌握。有兴趣的同学可查阅相关资料。

相对好理解一些的是归并排序(暂时不需要掌握代码),大家可以看动画的图片做相应的理解:

青少年Python编程系列36:排序算法和查找算法入门

归并排序

二、查找算法

2.1 顺序查找

顺序查找是一种最为常用的查找算法。我们生活中也经常会用到,比如我们要从一堆书里面找到我们想要的书,我们会从第一本开始一本一本地看,直到找到我们想要的那本书。

顺序查找的基本思想是从第一个元素开始,按顺序逐个将数据与给定的数据进行比较,如果某个数据与给定的数据相等,则查找成功,输出所查数据;反之则未找到。

顺序查找的代码使用Python实现也非常简单:

欢迎大家来到IT世界,在知识的湖畔探索吧!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]的中间位置。我们查找的过程中必然是以下三种情况之一:

  1. 如果key < a[m],key在前半部分,新的查找范围在[i, m-1]中
  2. 如果key = a[m],找到需要对数据
  3. 如果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) 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/37740.html

(0)
上一篇 2024年 1月 7日 下午6:00
下一篇 2024年 1月 8日 下午8:23

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信