资源简介

(共40张PPT)
专题六　排序、查找算法及应用
思维导图
归纳提炼
一、排序算法
1.排序
(1)排序的概念
排序是指将一些无序的数据变成有序的数据。
(2)排序方式
排序方式主要有:升序(从小到大排列)和降序(从大到小排列)。
(3)待排数据的存储方式
待排数据通常存储在数组或链表中。
2.常见的排序算法
常见的排序算法有:冒泡排序、选择排序、插入排序、二叉树排序、快速排序、堆排序、归并排序和桶排序等。
3.利用Python的sort方法和内建函数sorted方法排序
(1)sort方法
说明:使用sort方法对列表中的数据进行排序时,将直接对列表进行排序,不会产生新的序列。
例:列表lista=[36,23,12,17,22,19,28],可用命令lista.sort()将列表lista中的数据进行升序排序,可用命令lista.sort(reverse=True) 将列表lista中的数据进行降序排序。
(2)sorted函数
说明:使用sorted函数进行排序时,将排好序的数据返回一个新的序列。
例:lista=[36,23,12,17,22,19,28],执行语句listb=sorted(lista)后,列表listb中的元素为[12,17,19,22,23,28,36],从而实现升序排序;执行语句listc=sorted(lista,
reverse=True)后,列表listc中的元素为[36,28,23,22,19,17,12],从而实现降序排序。
4.冒泡排序
(1)冒泡排序的基本思想
冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整,让较大的数“下沉(上冒)”,较小的数“上冒(下沉)”的一种排序技术。
(2)冒泡排序的特点
①相邻两个数据进行比较。
②n个数据完成排序,共进行n-1趟(遍)排序。
④n个数据完成排序,其时间复杂度为O(n2)。
5.冒泡排序算法的程序实现
说明:对列表list1中的数据进行升序排序
def bubble_sort(list1):
count=len(list1)
#count个数排序共需进行count-1趟
for i in range(1, count):
#每一趟排序从前往后进行,比较相邻两个数
for j in range(0, count-i):
if list1[j]>list1[j+1]:
list1[j],list1[j+1]=list1[j+1],list1[j]
　　return list1
【归纳与提升】
(1)冒泡排序进行时,数据的比较可以由前往后进行,即list1[j]与list[j+1]比较;也可以由后往前进行,即list1[j]与list1[j-1]比较,此时应将循环条件“for j in range(0, count-i):”修改为“for j in range(count-1, i-1,-1):”。
(2)若要将数据按降序排序,只需将语句“if list1[j] > list1[j+1]:”修改为“if list1[j]二、顺序查找算法
1.查找(Search)
查找又称检索,计算机根据所给条件查找出满足条件的对象,即在存储的一批数据中寻找出一个特定的数据,或者确定在该批数据内是否存在这样的数据。
常见的查找算法主要有:顺序查找和二分查找(也称对分查找)。
2.顺序查找(Sequential Search)
顺序查找又称线性查找,是指从顺序表的一端开始,依次将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的关键字等于key,则表明查找成功;若所有元素都比较完毕仍找不到,则表明查找失败。
3.顺序查找算法基本框架
假设:要查找的数据为key,n个待查找的数存放在数组d中。
For循环实现:
　　find=False
　　for i in range(0,n):
if d(i)==key:　#则表示找到
修改find的值为True,并做相应处理
　　if find==False:
　　　表示未找到

While循环实现:
i=0
while i<=n-1:
　　　　if d(i)==key:　#则表示找到
　　　　　 修改find的值为True,并做相应处理
i=i+1
　　 if i==n,则表示未找到
4.顺序查找算法程序实现
假设:要查找的数据为key,n个待查找的数存放在数组d中,本程序找到满足条件的第一个数据就结束。
For循环实现 :
find=False
for i in range(n):
　 if key==d[i]:
　 find=True
　 print("find,索引号为:",i)
　　　if not find:
print("未找到")

while循环实现 :
i=0
while i<=n-1:
if key==d[i]:
print("find,索引号为:",i)
break
else:
i=i+1
　 if i==n:
print("未找到")
重难点剖析
(1)使用for循环查找时,需要设置一个逻辑变量,表示找到与否。
(2)while顺序查找还可以写为:
i=0
find=False
while i<=n-1 and not flag:
　　if key==d[i]:
　　　　print("find,索引号为:",i)
　　　　find=True
　　else:
　　　i=i+1
if i==n:　#或find==False
　print("未找到")
三、二分查找算法
1.二分查找(Binary Search)
二分查找又称对分查找或折半查找。
二分查找是指在有序的数据序列中,首先将查找键与有序数组内处于中间位置的元素进行比较,如果相等,则查找成功并退出查找;否则,根据数组元素的有序性,确定新的查找范围(在数组的前半部分还是后半部分);在确定了新的查找范围后,重复进行以上操作,直到找到或查找结束为止。
【归纳与提升】
①二分查找的前提条件是待查找的数据序列必须有序。
②“未找到”是指当前查找区间不存在,即区间左端点大于右端点。
2.二分查找的算法框架
说明:要查找的目标数据元素为key,待查找的数据元素存放在数组d中。
i、j分别为查找区间的起点位置和终点位置,m为查找区间的中间位置,n为数据元素个数。
i=0
j=n-1
while i<=j:
　　计算中点位置m
　　比较key与d[m],并做相应处理
若i>j,则表示未找到
3.二分查找的程序实现
·设要查找的数据是key,待查找的数据元素存放在数组d中,并已按升序排序。
·输出查找结果,若找到则输出信息“找到!位置为:X”,否则输出“查无此数!”
·输出查找次数c。
二分查找主要代码如下(以升序为例):
输入key的值
c=0　　　　　　　　　　　#记录查找次数
find=False #设置find的初值
i=0 #区间左端点位置
j=n-1 #区间右端点位置
while i<=j and not find: #还未找完并且还未找到,则继续查找
　　c=c+1 #查找次数记数
　　m=(i+j)∥2 #计算中点位置m,等价于m=Int((i+j)/2)
　　if key==d[m]: #找到目标元素,并进行相应处理
　 　　find=True
　 　　print(m)
　　if key>d[m]: #表示要查找的元素比中间位置上的元素大时
　 　　i=m+1 #调整区间左端点
　　else:
　　　j=m-1 #调整区间右端点
if find==False:
　print("查无此数!")
print("查找次数为:",c)
典型例题
[例1]采用冒泡排序对数据45,31,19,21,17,26,11,20进行降序排序,则排序完成时共进行数据交换的次数为(　 　)
A.6 B.7 C.8 D.9
B
解析:本题采用冒泡排序对数据进行降序排序,以从后往前进行数据比较为例,具体排序过程如下表所示:
原始数据 45 31 19 21 17 26 11 20 交换次数
第一遍 加工 45 31 26 19 21 17 20 11 4次
第二遍 加工 45 31 26 21 19 20 17 11 2次
第三遍 加工 45 31 26 21 20 19 17 11 1次
则数据交换次数为:4+2+1=7,因此答案为B。
[例2]对一组数据采用冒泡排序算法进行排序,若第一趟排序完成后的数据序列为:18,15,16,17,11,10,9,12,则该数据序列的初始顺序不可能是(　 　)
A.15,16,17,11,10,9,12,18 B.15,16,18,11,10,9,12,17
C.15,16,17,18,10,9,11,12 D.15,16,18,11,10,9,17,12
C
解析:从第一趟排序完成后的数据序列,可知本题的排序方式为降序,并从后往前进行相邻数据的比较和交换,若初始数据为15,16,17,18,10,9,11,12,则第一趟排序后的结果为18,15,16,17,12,10,9,11,与题目给出的第一趟排序结果不符,因此答案为C。
[例3]某二分查找算法的Python程序段如下:
n=int(input())
c=0
d=[1,2,3,4,5,6]
for k in range(0,len(d),n):
　 i=0;j=len(d)-1
　 key=d[k]
while i<=j:
m=(i+j)∥2
　　 　c+=1
　　　 if key==d[m]:
　　　　　break
　　 　elif key　　　　　j=m-1
　　 　else:
　　　　　i=m+1
print(c)
执行程序段后,输入以下不同的n 值,输出结果与其他三个不同的是(　 　)
A.2 B.3 C.4 D.5
C
解析:本题主要考查二分查找算法。首先根据二分代码画出二分查找树,如下图所示:
再观察 c 的累加查找次数,那可以先将每个值需要的查找次数先分别统计到数组a[2,3,1,3,2,3]中,然后题就转为:以步长n,从a中取值累加,经计算n = 2时,
c=2+1+2=5;n=3时,c=2+3=5;n=4时,c= 2+2=4;n=5 时,c=2+3= 5。故当n=4时,结果与其他几项不同,因此答案为C。
[例4]在n个数据元素中顺序查找某个特定元素是否存在,则最多比较次数、最少比较次数分别是(　 　)
A.0　n-1 B.1　n-1 C.1　n D.1　n+1
C
解析:根据顺序查找的思想,将给定的值与原数据进行逐个比较。若要找的数据元素刚好是第一个,则查找次数为1,因此最少的查找次数为1次;若要找的数据元素为最后一个或不存在时,则查找次数为n次,也是最多的查找次数,因此答案为C。
[例5]用链表实现数组的升序排序,Python 程序如下:
#生成无序数组,元素如[3,-1],分别表示数值和指针(指针初值均为-1),代码略
head=0
for i in range(1,len(a)):
　 q=head
　 p=a[head][1]
　 if a[head][0]>a[i][0]:
　　　a[i][1]=head
　　　head=i
　 else:
　　　 a[q][1]=i;a[i][1]=p
方框处应填入的代码是(　 　)
A. while p!=-1 and a[p][0]while p!=-1 and a[p][0]　 p=a[p][1]
　 q=p
C. while p!=-1 and a[q][0]while q!=-1 or a[p][0]　 q=p
　 p=a[p][1]
A
解析:本题主要考查链表与排序的综合应用。该算法中head固定在位置0,每轮均需要在已完成排序的链表中遍历,并把a[i]插入到q和p之间。本轮查找时,若p节点数据小于a[i]并且未到链表尽头(p不等于-1),则继续搜索,然后更新前置节点q和后继节点p。
[例6]数组a中的数据元素依次为“1,2,3,4,5,6,7,8”,利用二分查找算法查找元素5,需要查找的次数为(　 　)
A.1次 B.2次 C.3次 D.4次
解析:根据二分查找的算法思想,可以利用画二叉树来进行解题,如图所示。
第1次找到的中间元素为4,第二次key与6比较,第三次key与5比较,相等,则查找成功,因此需要查找的次数为3次,答案为C。
C
[例7]编写了一个成绩处理的程序,具体功能如下:程序运行时,首先从Excel文件中读取学生的数学成绩并存储在列表cj中,对数学成绩按从高分到低分进行排序;输入成绩key,统计并输出共有多少位同学的成绩大于等于该成绩。程序运行界面如下图所示。
数学成绩为:
[100,100,100,100,100,100,100,99,99,99,99,98,98,98,98,98,98,98,98,97,97,97,97,96,96,96,
96,96,96,96,95,95,95,95,95,94,94,94,94,94,94,93,93,93,92,92,91,91,91,91,91,91,91,91,90,
90,90,89,89,89,89,88,88,88,88,87,87,87,87,86,86,85,84,84,84,84,84,84,84,84,84,84,83,83,
83,83,83,83,83,83,83,82,82,82,82,82,81,81,80,80,80,79,79,79,79,79,79,79,79,79,79,79,79,
79,79,78,78,78,78,78,77,77,77,77,77,77,77,77,77,77,76,76,76,76,76,76,76,76,75,75,75,75,
74,74,74,73,73,73,72,72,72,72,71,71,71,71,70,70,70,70,69,69,69,69,69,69,69,69,68,68,68,
68,68,67,67,67,67,66,66,66,66,65,65,65,65,63,63,63,63,62,62,62,62,62,62,61,61,61,61,61]
please input key:98
共有19位同学大于等于该成绩
实现上述功能的Python程序如下,请在程序划线处填入合适的代码。
#从Excel文件中读取n个学生的数学成绩存储在数组cj中,代码略
n=len(cj)
print('数学成绩为:')
for i in range(0,n-1):
　　for j in range(　　　　①　　　　):
　　　if cj[j]>cj[j-1]:
　　　　 cj[j],cj[j-1]=cj[j-1],cj[j]
print(cj)
key=int(input("please input key:"))
i=0
j=n-1
while i<=j:
　　m=(i+j)∥2
　　if 　　　　②　　　　:
　　　j=m-1
　　else:
　　　i=m+1
print("共有" +　　　　③　　　　+ "位同学大于等于该成绩。")
程序划线①处应填入的代码为:　　　　　　　　　　　　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　　　　　　　　　　;
程序划线③处应填入的代码为:　　　　　　　　　　　　　　　　　。
n-1,i,-1　
key>cj[m]　
str(i)
解析:本题主要考查的是冒泡排序和二分查找。本题采用冒泡排序对数组中的元素进行降序排序,根据代码“if cj[j]>cj[j-1]”,可知数据比较是从后往前进行的,n个数据排序,共进行n-1趟,第i趟时,j的值从n-1~i+1,因此程序①处代码为n-1,i,-1;然后使用二分查找算法在数组cj中查找第一个大于等于key的数据元素,因此程序②处代码为key>cj[m];因为数据是降序排序,所以大于等于key的元素个数为i个,由于print命令中使用“+”运算符,因此需将“i”转换为字符类型,即划线③处代码为str(i)。
感谢观看

展开更多......

收起↑