选择性必修1 专题六 排序、查找算法及应用-【导与练】2024高考信息技术一轮复习高中总复习第1轮教学课件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]<list1[j+1]:”即可。 二、顺序查找算法 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