2022选考复习系列之一（冒泡排序复习）【新教材】浙教版(2019)高中信息技术选择性必修一《数据与数据结构》

冒泡排序复习浙教版新教材(2019)《数据与数据结构》选择性必修1——冒泡排序复习经典冒泡从后往前冒，以下演示从前往后冒2

345101505第一遍：比较5次，交换2次经典冒泡从后往前冒，以下演示从前往后冒2

34105第一遍：比较5次，交换2次第二遍：比较4次，交换2次1404经典冒泡从后往前冒，以下演示从前往后冒2

3104

5第一遍：比较5次，交换2次第二遍：比较4次，交换2次3130第三遍：比较3次，交换2次经典冒泡从后往前冒，以下演示从前往后冒2

103

4

5第一遍：比较5次，交换2次第二遍：比较4次，交换2次第三遍：比较3次，交换2次2120第四遍：比较2次，交换2次经典冒泡从后往前冒，以下演示从前往后冒1

02

3

4

5第一遍：比较5次，交换2次第二遍：比较4次，交换2次第三遍：比较3次，交换2次第四遍：比较2次，交换2次10第五遍：比较1次，交换1次经典冒泡：从前往后与从后往前，总比较次数和交换次数不变，排序遍数n-1一、冒泡排序思想排序遍数是？比较次数？交换次数？1、2组从前往后冒3、4组从后往前冒一、冒泡排序思想冒泡排序思想总结：★升序：将后数小于前数的两个数进行交换；降序：将后数大于前数的两数进行交换★n个数最多进行

n-1遍排序★两数比较的次数为:n*(n-1)/2★两数交换次数最多为：

n*(n-1)/2升序核心代码foriinrange(0,n-1):forjinrange(n-1,i,-1)ifa[j]<a[j-1]:

交换a[j]与a[j-1]控制遍数为n-1遍即可初值定，控制每遍冒泡方向和比较次数，一般为n-1/n-2或0,1。终值与i和前后项表达相关。初值和终值不能换位置。控制次序——后项<前项，交换，升序。表达方法a[j-1]或a[j+1],从j初值可得二、冒泡排序程序实现(一维数组为例)课堂练习7.

D三、冒泡排序应用观察d变量，有哪些特征？三、冒泡排序应用编程实现，以左图形式显示三、冒泡排序应用1编程实现，按总分高到低排序三、冒泡排序应用2编程实现，女生在前，男生在后，分别按降序排序三、冒泡排序应用3编程实现，男生在前，降序排序，女生在后，升序排序三、冒泡排序应用3还有哪些排序形式？出现同分情况怎么处理？只排男生或只排女生？(位置不变）只排前三名不改变原有顺序排序？四、冒泡排序优化1——遍数优化foriinrange(1,len(d)):

flag=False

forjinrange(0,len(d)-i):ifd[j]>d[j+1]:

flag=Trued[j],d[j+1]=d[j+1],d[j]

ifflag==False：

break标记是否存在交换变量flag，默认无序有交换，则标记True内循环结束如无交换，则表明有序一、冒泡排序优化1——遍数优化i=1;flag=FalseWhilei<len(d)andflag==False

flag=True

forjinrange(0,len(d)-i):ifd[j]>d[j+1]:

flag=False

d[j],d[j+1]=d[j+1],d[j]

i+=1notflag课堂练习1.有如下Python程序段：d=[173,172,169,178,183]foriinrange(1,len(d)):c=0forjinrange(0,len(d)-i):ifd[j]>d[j+1]:c+=1

d[j],d[j+1]=d[j+1],d[j]ifc==0:

break则程序运行之后，i的值为（）A.1B.2C.3D.4cd=[173,172,169,178,183]foriinrange(1,len(d)):forjinrange(0,len(d)-i):ifd[j]>d[j+1]:c+=1

d[j],d[j+1]=d[j+1],d[j]则程序运行之后，c的值为（

）A.10B.8C.5D.3D课堂练习2.若冒泡排序在某一遍加工过程中没有数据交换，则说明数据已经有序，优化程序段如下：a=[58,36,23,97,77]n=len(a);i=1;flag=Truewhilei<=4andflag==True:

flag=Flaseforjinrange(4,i-1,-1):ifa[j]>a[j-1]:a[j],a[j-1]=a[j-1],a[j];flag=True

i+=1数组元素a[0]到a[4]的值依次为“58,36,23,97,77”，经过该程序段“加工”后，变量i的值是___________。4四、冒泡排序优化2——范围优化当某一遍加工过程中没有数据交换，说明数据已经有序，无需进一步加工。当某段数据某遍加工过程中未发生任何一次数据交换，说明该段数据已经有序，无需进一步加工，只需处理其后数据即可。下次冒泡只需比较到最后记录的位置，因为前段有序。四、冒泡排序优化2——范围优化last=len(d)-1foriinrange(1,len(d)):

c=0

forjinrange(0,last):ifd[j]>d[j+1]:

c+=1;d[j],d[j+1]=d[j+1],d[j]

last=jifc==0:break有如下Python程度段生成随机数组a并将其中的元素从小到大排序：importrandoma=[0]*10;

i=0x=random.randint(1,100)whilei<10：ifxnotina：a[i]=x;i=i+1x=random.randint(1,100)i=0whilei<9：

k=I

;i=9forjinrange(9,k,-1)：ifa[j]<a[j-1]:a[j],a[j-1]=a