5.3.1 数据排序 课件（27张PPT）.pptxVIP

5.3数据排序(一)——冒泡排序册别：选择性必修1学科：高中信息技术(浙教版)

学习目标：能理解冒泡排序的算法思想。能合理选用数据结构，理清冒泡排序的范围与条件。能用自然语言、流程图、Python语言描述冒泡排序算法。能分析冒泡排序次数、比较次数和交换次数。能掌握优化冒泡排序方法。

想一想：给下列5位同学从低到高排好队、

想一想：给下列5位同学从低到高排好队、

排序概念：、排序：就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。排序前：排序后：数组形式存储链表形式存储

体验：Python中，对列表排序的方法一、列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列二、内建函数sorted方法，返回一个新的序列，原来的序列依然存在reverse=True降序默认：reverse=False升序

冒泡排序[递增]的方法是冒泡排序[BubbleSort]是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉”（“上冒”），较小的数“上冒”（“下沉”）的一种排序技术。每一遍加工都是将本遍中最大的元素“下沉”至本遍的底端位置——从前往后，升序每一遍加工都是将本遍中最小的元素像气泡一样“上浮”至本遍的顶端位置——从后往前，升序

冒泡排序：第一遍（i=1)加工后，冒泡范围j:[0,n-1]，最后一个元素d[4]最大第二遍（i=2)加工后，冒泡范围j:[0,n-2]，倒数第二个元素d[3]次大第三遍（i=3)加工后，冒泡范围j:[0,n-3]，倒数第三个元素位置固定第四遍（i=4)加工后，冒泡范围j:[0,n-4]，倒数第四个元素位置固定对5(n)个元素数组d从前往后冒泡升序排序第一个与第二个元素关注1：每趟（第i遍）相邻（j与j+1位置)两两比较的起点关注2：每趟（第i遍）相邻（j与j+1位置)两两比较的终点n-i

冒泡排序[递增]的方法是对于n个元素，第一遍加工将最大元素下沉到第n个位置对于剩下的n-1元素，反复使用该规则，直到最后余下两个元素进行比较和交换冒泡排序完成

冒泡排序标准程序的流程图描述：开始i←1,L←len(d)i=L-1?j=0jL-i?d[j]d[j+1]?j=j+1输出已排序数组d结束i=i+1互换d[j]与d[j+1]是是是否否否（1）（2）（3）

冒泡排序（递增）#参考教材P131d=[12,5,23,6,2]n=len(d)#外循环i取1-n-1共n-1次处理#内循环从前往后冒：起点0与1位置上的元素，终点每次处理后往前缩进1#相邻两两比较后，大数往后冒，两数互换forjinrange(n-i):foriinrange(1，n):ifd[j]d[j+1]:d[j],d[j+1]=d[j+1],d[j]print(排序后的列表,d)用Python语言编写程序并调试

d=[5,3,7,8,1,9,2,6]n=len(d)i=0whilein-1:j=0while:ifd[j]d[j+1]:d[j],d[j+1]=d[j+1],d[j]j+=1i+=1print（“排序后的列表”,d）#外循环i取0至n-2共n-1次加工#大数往后冒，两数互换#内循环每趟从第一个与第二个元素比较开始#升序填一填：假如我们实现从前往后冒泡的升序排列，请问划线处填什么？jn-1-ij+1jn-2-in-1-i

填一填：d=[5,3,7,8,1,9,2,6]n=len(d)foriinrange(n-1):forjinrange(n-i-1):if:d[j],d[j+1]=d[j+1],d[j]print(“排序后的列表”,d)#外循环i取0-n-2共n-1次加工#小数往后冒，两数互换#内循环从前往后冒#降序假如我们实现从前往后冒泡的降序排列，请问划线处填什么？d[j]d[j+1]

冒泡排序（从后往前升序）：d=[5,3,7,8,1,9,2,6]n=len(d)print(排序后的列表,d)#小数往前冒，升序排列#内循环从后往前冒,每次都是从第n-1与n-2位置上元素比较开始,至第i个结束ifd[j]d[j-1]:d[j],d[j-1]=d[j-1],d[j]#外循环i取0-n-2共