选择性必修1 专题六 排序、查找算法及应用-【导与练】2024高考信息技术一轮复习高中总复习第1轮教师用书word(浙江专用)

| 27页
| 299人阅读
| 10人下载
教辅
山东瀚海书韵教育科技有限公司
进店逛逛

学科网 zxxk.com学科网 zxxk.com

学科网 zxxk.com

专题六 排序、查找算法及应用

一、排序算法

1.排序

(1)排序的概念

排序是指将一些无序的数据变成有序的数据。

(2)排序方式

排序方式主要有:升序(从小到大排列)和降序(从大到小排列)。

(3)待排数据的存储方式

待排数据通常存储在数组或链表中。

2.常见的排序算法

常见的排序算法有:冒泡排序、选择排序、插入排序、二叉树排序、快速排序、堆排序、归并排序和桶排序等。

3.利用Python的sort方法和内建函数sorted方法排序page number 0

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司

学科网 zxxk.com


学科网 zxxk.com学科网 zxxk.com

学科网 zxxk.com

(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个数据完成排序,数据的比较次数为 。page number 1

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司

学科网 zxxk.com


学科网 zxxk.com学科网 zxxk.com

学科网 zxxk.com

④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)page number 2

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司

学科网 zxxk.com


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。