高中信息技术浙教版（2019）选修1 第五章　课时3　数据排序（学案 课件，2份打包）

(课件网) 课时3　数据排序 第五章　数据结构与算法 1.通过具体实例，理解排序的概念和基本方法。2.能根据实际的应用场景，选择合理的数据结构，并使用排序算法来编程解决问题。 目 录 CONTENTS 知识梳理 01 例题精析 02 随堂检测 03 巩固与提升 04 知识梳理 1 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，resverse＝True)后，列表listc中的元素为[36，28，23，22，19，17，12]，从而实现降序排序。 新的序列 4.冒泡排序 (1)冒泡排序的基本思想 冒泡排序是在数列中对_____两个数据依次进行_____和位置调整，让较大的数“下沉(或上冒)”，较小的数据“上冒(或下沉)”的一种排序技术。 (2)冒泡排序的特点 ①_____两个数据进行比较。 ②n个数据完成排序，共进行_____趟(遍)排序。 ④n个数据完成排序，其时间复杂度为_____。 相邻 比较 相邻 n－1 O(n2) 5.冒泡排序算法的程序实现 说明：对列表list1中的数据进行升序排序 def bubble_sort(list1)： count＝len(list1) #count个数排序共需进行count－1趟 for i in range(1，count)： #每一趟排序从前往后进行，比较相邻两个数 for j in range(_____)： 　　　　　　if _____： 　　　　　list1[j]，list1[j＋1]＝list1[j＋1]，list1[j] return list1 0，count－i list1[j]>list1[j＋1] (1)冒泡排序进行时，数据的比较可以由前往后进行，即list1[j]与listl[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]