5.3 数据排序（教学课件）信息技术浙教版2019选择性必修1

第3节 数据排序（2课时） 第5章 数据结构与算法 浙教版（2019） 选修一 排序 01 常见的排序算法 02 排序算法的应用 03 学习目录 了解排序的主要作用，掌握排序的基本概念，知道常用的排序算法。 01 能够完整地进行抽象与建模、设计算法与数据结构、程序实现，解决排序算法的应用问题。 03 熟练掌握冒泡排序的基本思想和基本程序结构，并能够编程实现冒泡排序。 02 学习目标 PART 01 排序 新课导入 看 看 一 新课导入 想 想 一 上图中都是生活中常见的一些排队或者可以说是排序。 我们在日常生活中会经常经历排序的场景，比如体育课上按身高排列等等熟悉的生活体验。这种熟悉的经验，在计算机中的排序又有哪些? 问题： 新课导入 同学们对于电脑并不陌生，在计算机软件系统中，排序是一种常见的操作。 如文件夹中图片文件可分别按名称、大小、类型、修改日期等方式进行排序；电子邮件列表一般按照日期排序，最新的邮件被放置在最顶端；购物网站上搜索到的某类商品可按价格、销量、信用等方式进行排序。 什么是排序？ 排序 一 概念 将无序数据按照某种规则(递增或递减)，重新排列使其变成有序数据。 (元素的入 对一次具体排序而言，总是针对某一组数据元素的某种具体的序关系进行操作。 通过关键字之间的比较判断，将数据移到合适的位置 对链表进行排序无须移动数据，只需修改指针即可 未排序数据的存储方式 以数组作为存储结构 以链表作为存储结构 排序 一 计算机要对数据排序，先要考虑数据的组织形式。如果有一组数(23，20，13，18，14，11)分别存储以数组、链表的形式，排序有什么不同呢? 数据存储情况 排序 一 为了分析问题方便，我们以后假设数据以数组形式存储，然后讨论它的排序算法。排序的基本要求是什么? (元素的入 以数组为例，每个数组元素都对应存储一个数据。 例如，存储在数组元素d[0]中的数据是23，d[1]中存储的是20，等等。 如果对数组d中的6个数据按升序进行排序，即调整数组d中所有数据的存储位置，使最小的数据存储在d[0]中，次小的数据存储在d[1]中……最大的数据存储在d[5]中。数组d中的所有数据满足：d[0]≤d[1]≤d[2]≤d[3]≤d[4]≤d[5]。这里两个数组元素的比较：d[i]≤d[j] (i=0,1,…,5; j=0,1,…,5)，指的是d[i]中的数据小于或等于d[j]中的数据。 对数组d按升序进行排序后，数据的存储情况如下图所示： 排序后的数据存储情况 排序 一 总结 排序(sorting)就是整理数据的序列，使其中元素按照某个值的递增(或递减)的次序重新排列的操作。在排序的过程中，序列里的数据元素的值保持不变，但其排列顺序可能改变。 排序 一 只需知道数据之间相互链接的顺序 探讨与讨论 一 对“842715”中的数字进行选择排序中的两遍“加工”即为某密码锁 的密码，则该密码可能是( ) A.842715 B.142785 C.872415 D.124578 C 排序 一 只需知道数据之间相互链接的顺序 探讨与讨论 二 对下列一组原始数组:13，15，2，11，8，18进行选择排序，第一趟排序介绍，数组的状态不可能是（ ） A.2，15，13，11，8，18 B.18，15，2，11，8，13 C.13，15，2，11，18，8 D.13，15，18，11，8，2 C PART 02 常见的排序算法 常见的排序算法 二 拓展链接 Python中，对列表进行排序的方法有两种：一种是列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列；另外一种是内建函数sorted方法，返回一个新的序列，而原来的序列依然存在。两者的使用方法如右表所示： >>> a=[5,7,6,3,4,1,2] >>> b=sorted(a) >>> print(a) [5, 7, 6, 3, 4, 1, 2] >>> print(b) [1, 2, 3, 4, 5, 6, 7] >>>a.sort() >>> print(a) [1, 2, 3, 4, 5, 6, 7] >>>a.sort(reverse=True) #reverse=True实现降序排序 >>> print(a) [7, 6, 5, 4, 3, 2, 1] Python中的排序函数 常见的排序算法 二 在一次电视节目上,谷歌总裁施密特提出问题:“如何才能更有效地对一百万个32位长整数进行排序?”同在现场的奥巴马总统立刻响应道:“肯定不能用冒泡排序法。”施密特评价说:"天哪!他是从谁那里听说这个的。” 这里奥巴马总统提到的“冒泡排序”，它是如何进行的呢? 常见的排序算法 二 冒泡排序（Bubble Sort）是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 常见的排序算法 二 以升序为例 第一遍 加工 冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据，对相邻两个数进行比较，将较小的数据换到上面的一个元素中（或将较大的数据换到下面的一个元素中）。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。 当第一遍加工完成时，数 据 结 构与算法最小的数据已经“上浮”到第一个元素的位置（或最大的数据“下沉”到最后一个元素的位置）。然后对余下的n–1个元素重复上述处理过程，直至最后进行余下两个数据的比较和交换。由于每一遍加工都是将本遍最小的元素像气泡一样“上浮”至本遍的顶端位置（或将本遍最大的元素“下沉”至本遍的底端位置），故称为冒泡排序。 常见的排序算法 二 第一遍加工完毕，最大值23“下沉”至数组最后一个元素的位置。即第一遍加工，先比较相邻两元素d[0]与d[1]，不符合所要求的顺序，则交换两者的位置；再比较调整d[1]与d[2]……最后比较调整d[4]与d[5]。 冒泡排序算法对数组d的第一遍加工过程 常见的排序算法 二 13 20 18 14 11 23 13 18 20 14 11 23 13 18 14 20 11 23 13 18 14 11 20 23 20 13 18 14 11 23 d[0] d[1] d[2] d[3] d[4] d[5] 第二遍加工 初始值 第二轮排序时，只排到导数第二个...以此排完。 常见的排序算法 二 若要排序的数有n个，则需要n–1遍加工。第i遍加工中，从第一个数开始，相邻两数比较，若反序则交换两者的位置，直到第n+1–i个数为止。第一个数与第二个数比较，第二个数与第三个数比较……第n–i个与第n+1–i个比较，共比较n–i次。此时第n+1–i个位置上的数已经按要求排好，所以不参加以后的比较和交换操作。 对n个元素的数组，用冒泡排序算法进行排序时，共需比较： (n–1)+(n–2)+…+1= （次） 其时间复杂度为〇(n 2 )。 常见的排序算法 二 记录正进行的处理遍数，第1遍处理时值为1，第2遍处理时值为2，以此类推。 记录当前数组元素的下标。每遍处理过程中，j值总是从第一个数组元素的下标值0开始，按每次加1的方式，直至j=n–i–1为止。每当j取定一个值后，当前数组元素d[j]将与它的后一个元素d[j+1]进行比较，若d[j] ＞d[j+1]，则互换这两个数组元素中的数据。 排序过程中，按右面的方式使用变量i和j 变量i 变量j 常见的排序算法 二 冒泡排序算法对数组d的5遍加工过程 常见的排序算法 二 对规模为n的数组d，冒泡排序的算法流程图如右图所示。 冒泡排序的算法流程图 常见的排序算法 二 代码实现： def bubble_sort(d): length=len(d) #序列长度为length，需要执行length–1遍加工 for i in range(1,length): for j in range(0,length–i): if d[j]>d[j+1]: temp=d[j] d[j]=d[j+1] d[j+1]=temp 常见的排序算法 二 (元素的入 在选取排序算法时，可以根据待排序数据自身的特点来选择相应的算法。 时间 复杂度 空间 复杂度 稳定性 常见的排序算法 二 只需知道数据之间相互链接的顺序 探讨与讨论 一 某场篮球联赛中，有5个班级的比赛积分依次为14,11,13,8,9。若 采用冒泡排序算法从右到左对其进行升序排序，则第二轮排序后的结果是 ( ) A.8,11,13,14,9 B.8,9,13,14,11 C.8,9,14,11,13 D. 14,13,11,9,8 C 常见的排序算法 二 只需知道数据之间相互链接的顺序 探讨与讨论 二 某 Python程序如下： a=[3,1,9,7,6,3] n=len(a) for i in range(1,n): for j in range(n-2,i-2,- 1): if a[jka[j+1]: a[j],a[j+1]=a[j+1],a[j] 程序运行后，数组a的值是（ ） A.[9,3,1,7,6,3] B.[9,7,6,3,3,1] C.[1,3,3,9,7,6] D.[1,3,3,6,7,9] B PART 03 排序算法的应用 排序算法的应用 三 同学们，这本书和字典你们都认识吗？都使用过，你们在使用字典或翻书的时候，都是按照其中的顺序进行查找的。 排序能使数据有序，而有序的数据更加便于使用。 排序算法的应用 三 排序算法在实际生活中的应用 奥运成绩排行榜 每届奥运会各大媒体都会公布一个成绩排行榜，但每个排行榜可能略有不同，如有的是按金牌总数排列的“金牌榜”，有的是按奖牌总数排列的“奖牌榜”，甚至还有“国民人均奖牌榜”，等等。现在，以2008年北京奥运会的奖牌数为例，部分数据（数据统计时间为2008年8月25日）。请你编写一个程序，编制金牌排行榜。 排序算法的应用 三 编号 国家/地区 人口数量（万） 金牌（枚） 银牌（枚） 铜牌（枚） 总数（枚） 8 中国 136407 51 21 28 100 20 印度 130420 1 0 2 3 53 美国 32262 36 38 36 110 21 印度尼西亚 26110 1 1 3 5 13 巴西 20529 3 4 8 15 23 尼日利亚 18231 0 1 3 4 52 俄罗斯 14253 23 21 28 72 6 日本 12703 9 6 10 25 2008年北京奥运会奖牌数表 排序算法的应用 三 抽象与建模 从表中的数据可以看出，每个国家的信息是一条记录，包括编号、国家/地区、人口数量、各奖牌数等数据项。编制金牌排行榜，要按排序关键字“金牌”降序排序。排序过程中若要交换，则要将待交换的两条记录整 体进行交换。 排序算法的应用 三 设计算法与数据结构 1 第一种方案： 采用7个一维数组按列存储，即每个数组分别存储每个国家的编号、国家/地区、人口数量、各奖牌数等，如定义b数组存储表中8个国家的金牌数量，其对应的值为[51,1,36,1,3,0,23,9] ； 2 第二种方案： 采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如[8,"中国",136407,51,21,28,100]对应中国的相关信息。 排序算法的应用 三 采用不同的存储方式，排序时数据的交换方式也有不同： 01 若采用7个一维数组按列存储，排序过程中，两条记录的对应数据项都要相应交换，即要考虑7个一维数组的操作。 02 若采用1个一维数组按行存储，排序中的数据交换可对整条记录进行交换操作。 排序算法的应用 三 编写程序 若存储结构采用1个一维数组，以金牌数为关键字进行降序排序，程序如右： import csv #数据读入 csvFile=open("jp.csv", "r") #打开相应数据文件 reader=csv.reader(csvFile) #建立一个读入数据的对象 a=[] for item in reader: a.append(item) csvFile.close() #排序 for i in range(1,len(a)–1): #排序不包含第一行数据 for j in range(1,len(a)–i): if int(a[j][3])<int(a[j+1][3]): temp=a[j] a[j]=a[j+1] a[j+1]=temp #数据写入 csvFile2=open('jp2.csv','w', newline='') writer=csv.writer(csvFile2, dialect='excel') m=len(a) for i in range(m): writer.writerow(a[i]) csvFile2.close() 程序中的“a[j][3]”表示某条记录索引位置为3的信息，即某个国家的金牌数。而“a[j]=a[j+1]”表示整条记录的所有信息的赋值。 排序算法的应用 三 只需知道数据之间相互链接的顺序 探讨与讨论 一 有如下Python 程序段: A=[15,20,11,6,12,8,7,3] for i in range(1,3): for j in range(0,8-i): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] 程序段运行后,数组a中的数据依次为（ ） A.3,6,7.8.11.12.15,20 B15,11.6,12,8,7.3,20 C.11,6,12,8.7,3,15,20 D.6,11,8.7.3.12.15.20 C 课堂小练 四 1.采用冒泡排序算法对数据序列“7，3，8，2，1，9”进行排序，第一轮排序后的结果为“3，7，2，1，8，9”则完成整个排序需要交换的次数是( ) A.6次 B.7次 C.8次 D.9次 2.在某篮球赛季中，明星队6场比赛得分依次为103,77,95,71,68,89,若采用冒泡排序算法对其进行排序，第一轮排序结果是68,103,77,95,71,89.则第三轮排序中共进行 次数据交换。 C 1 课堂小练 四 只需知道数据之间相互链接的顺序 探讨与讨论 三 有如下 python 程序段： n=6 a = [] for i in range(3): for j in range(n - i - 1): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] print(a) 数组元素a（1）到a（6）的数据依次为“50，31，18，42，37，23”，则此程序运行完成后数组元素的数据依次是（　 　） A. 50，42，37，31，23，18 B. 18，23，31，50，37，42 C. 18，31，23，37，42，50 D. 18，23，31，37，42，50 C 小结 四 数据排序 小 结 一、排序 1.概念 2.存储方式 数组、链表 二、常见的排序算法 1.拓展链接：Python中的排序函数 列表自带的sort方法、内建函数sorted方法 2.冒泡排序 冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 三、排序算法的应用 谢谢观看 第3节 数据排序 浙教版（2019） 选修一 $$