5.3.1 数据排序之冒泡排序 ppt课件（共25张PPT）-2023新浙教版《高中信息技术》选择性必修第一册.pptx

1、数据排序数据排序排序排序就是整理数据整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。在排序的过程中，数据元素的值保持不变，但其在序列中的顺序顺序可能会改变。对于一次具体排序而言，总是针对某一组数据元素某一组数据元素的某种具体的序关系进行操作。待排序数据的存储方式一般有两种：一种是将数据依次存放在一组地址连续的存储单元中，即以数组数组作为存储结构。在这种情况下，排序过程是对数据本身进行物理重排物理重排，即通过关键字之间的比较判断，将数据移到合适的位置。另一种存储方式是以链表链表作为存储结构，排序过程中无须移动数据，仅需修改指针修改指针即可。以数组为例，每个数组元素都对应

2、存储一个数据。如下图所示，存储在数组元素d0中的数据是23，d1中存储的是20，等等。232320201313181814141111d012345如果对数组d中的6个数据按升序升序进行排序，即调整数组d中所有数据的存储位置，使最小的数据存储在d0中，次小的数据存储在d1中最大的数据存储在d5中。数组d中的所有数据满足：d0d1d2d3d4d5。这里两个数组元素的比较：didj(i=0,1,5;j=0,1,5)，指的是di中的数据小于或等于dj中的数据。对数组d按升序进行排序后，数据的存储情况如下图所示。111113131414181820202323d012345Python中，对列表进行排

3、序的方法有两种：一种是列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列；另外一种是内建函数sorted方法，返回一个新的序列，而原来的序列依然存在。两者的使用方法如下所示：a=5,7,6,3,4,1,2b=sorted(a)print(a)5,7,6,3,4,1,2print(b)1,2,3,4,5,6,7a.sort()print(a)1,2,3,4,5,6,7a.sort(reverse=True)#reverse=True实现按降序排序print(a)7,6,5,4,3,2,1冒泡排序冒泡排序冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下

4、沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。23232013181411d5d4d3d2d1d02020231318141120201323181411202013182314112020131814231120201318141123冒泡排序算法对数组冒泡排序算法对数组d d的第一遍加工过程的第一遍加工过程冒泡排序算法对数组冒泡排序算法对数组d d的第二遍加工过程的第二遍加工过程2020131814112313132018141123131318201411231313181420112313131814112023冒泡排序算法对数组冒泡排序算法对数组d d的第三遍加工过程的第三遍

5、加工过程13131814112023131318141120231313141811202313131411182023冒泡排序算法对数组冒泡排序算法对数组d d的第四遍加工过程的第四遍加工过程131314111820231313141118202313131114182023冒泡排序算法对数组冒泡排序算法对数组d d的第五遍加工过程的第五遍加工过程1313111418202311111314182023O(nO(n2 2)排序过程中，按下面的方式使用变量i和j:i:记录正进行的处理遍数，第1遍处理时值为1，第2遍处理时值为2，以此类推。j:记录当前数组元素的下标。每遍处理过程中，j值总是从第

6、一个数组元素的下标值0开始，按每次加1的方式，直至j=n-i-1为止。每当j取定一个值后，当前数组元素dj将与它的后一个元素dj+1进行比较，若djdj+1，则互换这两个数组元素中的数据。如下图所示是6个元素进行5遍加工的过程。23232013181411d5d4d3d2d1d020201318141123jj+1i=113131814112023i=313131411182023i=213131114182023i=411111314182023i=5对规模为n的数组d，冒泡排序的算法流程图如图所示：开始是i 1,L njL-i?j 0iL-1?是djdj+1?i i+1否交换dj和dj+1

7、否j j+1是输出结果结束否程序代码实现：程序代码实现：def bubble_sort(d):length=len(d)#序列长度为length，需要执行length-1遍加工 for i in range(1,length):for j in range(0,length-i):if djdj+1:temp=dj dj=dj+1 dj+1=temp冒泡排序迁移应用及原理1.冒泡排序迁移应用一（升序）for i in range(1,n):for j in range(n-1,i-1,-1):if ajaj-1:temp=aj aj=aj-1 aj-1=temp迁移原理：每一遍冒泡都是从后往前

8、两两比较的，因此每遍排序达到的效果是把最小值推到了最前面。2.冒泡排序迁移应用二（升序）n=len(a)for i in range(n-1):for j in range(n-2,i-1,-1):if aj+1ai:ai,aj=aj,ai迁移原理：在第i遍的排序中，把索引为i+1到索引为n-1的数组元素依次与ai比较，如果比ai小，则两两交换。它的特点是所有的数与一个固定位置上的数进行比较。排序过程中，自前向后将数据进行有序排列。4.冒泡排序的优化迁移当某一遍排序过程中没有数据发生交换时，说明数据已经有序已经有序，无需进行下一遍排序，代码如下：n=len(a)flag=True#flag值为

9、True表示一遍加工中发生过交换i=1while i=n-1 and flag=True:flag=False for j in range(n-1,i-1,-1):if ajaj-1:aj,aj-1=aj-1,aj flag=True i+=1迁移原理：用一个逻辑变量flag标记某一遍排序过程中是否有数据交换另一种写法：n=len(a)flag=True#flag值为True表示一遍加工中发生过交换i=1while i=n-1 and flag=True:flag=False for j in range(n-1,i-1,-1):if ajaj-1:aj,aj-1=aj-1,aj flag=

10、True if flag=False:break i+=1迁移原理：这种写法的排序遍数是i，在循环体内遇到了break语句，程序跳出该循环，不再执行“i+=1”指令。练一练1.采用冒泡排序算法对数据序列“1,7,2,5,12,15,27,10,6,30”完成升序排序，理论上讲共需进行排序的遍数为（）A.6遍 B.7遍 C.8遍 D.9遍2.采用冒泡排序算法对数据序列“2,15,7,5,9,18,30,25”完成降序排序，共需进行数据交换的次数为（）A.21次 B.22次 C.23次 D.24次D DC C3.采用冒泡排序算法对8个数据“18,15,9,3,7,5,16,21”进行降序排序，则第

11、2遍的排序结果是（）原始数据原始数据18,15,9,3,7,5,16,2118,15,9,3,7,5,16,21第1遍完成后的数据为21,18,15,9,3,7,5,16第2遍完成后的数据为第3遍完成后的数据为A.21,18,16,15,9,7,5,3B.21,18,16,15,9,3,7,5C.21,18,16,15,9,7,3,5D.21,18,16,15,9,3,5,7B B4.若冒泡排序在某一遍加工过程中没有数据交换，则说明数据已经有序，优化程序段如下：a=58,36,23,97,77n=len(a)i=1flag=Truewhile iaj-1:aj,aj-1=aj-1,aj flag=True i+=1数组元素a0到a4的值依次为“58,36,23,97,77”，经过该程序段“加工”后，变量i的值是_。4 4谢 谢