(
课件网) 冒泡排序复习 浙教版新教材(2019)《数据与数据结构》选择性必修1———冒泡排序复习 经典冒泡从后往前冒，以下演示从前往后冒 2 3 4 5 1 0 1 5 0 5 第一遍：比较5次，交换2次 经典冒泡从后往前冒，以下演示从前往后冒 2 3 4 1 0 5 第一遍：比较5次，交换2次 第二遍：比较4次，交换2次 1 4 0 4 经典冒泡从后往前冒，以下演示从前往后冒 2 3 1 0 4 5 第一遍：比较5次，交换2次 第二遍：比较4次，交换2次 3 1 3 0 第三遍：比较3次，交换2次 经典冒泡从后往前冒，以下演示从前往后冒 2 1 0 3 4 5 第一遍：比较5次，交换2次 第二遍：比较4次，交换2次 第三遍：比较3次，交换2次 2 1 2 0 第四遍：比较2次，交换2次 经典冒泡从后往前冒，以下演示从前往后冒 1 0 2 3 4 5 第一遍：比较5次，交换2次 第二遍：比较4次，交换2次 第三遍：比较3次，交换2次 第四遍：比较2次，交换2次 1 0 第五遍：比较1次，交换1次 经典冒泡：从前往后与从后往前，总比较次数和交换次数不变，排序遍数n-1 一、冒泡排序思想 排序遍数是？比较次数？交换次数？ 1、2组从前往后冒 3、4组从后往前冒 一、冒泡排序思想 冒泡排序思想总结： ★ 升序：将后数小于前数的两个数进行交换；降序：将后数大于前数的两数进行交换 ★ n个数最多进行 n-1 遍排序 ★ 两数比较的次数为: n*(n-1)/2 ★ 两数交换次数最多为： n*(n-1)/2 升序 核心代码 for i in range(0,n-1): for j in range(n-1,i,-1) if a[j]
d[j+1]: flag=True d[j],d[j+1]=d[j+1],d[j] if flag==False： break 标记是否存在交换变量flag，默认无序 有交换，则标记True 内循环结束如无交换，则表明有序 一、冒泡排序优化1———遍数优化 i=1 ; flag=False While id[j+1]: flag=False d[j],d[j+1]=d[j+1],d[j] i+=1 not flag 课 堂 练 习 1. 有如下Python程序段： d=[173,172,169,178,183] for i in range(1,len(d)): c=0 for j in range(0,len(d)-i): if d[j]>d[j+1]: c+=1 d[j],d[j+1]=d[j+1],d[j] if c==0: break 则程序运行之后，i的值为（ ） A. 1 B. 2 C. 3 D. 4 c d=[173,172,169,178,183] for i in range(1,len(d)): for j in range(0,len(d)-i): if d[j]>d[j+1]: c+=1 d[j],d[j+1]=d[j+1],d[j] 则程序运行之后，c的值为（ ） A. 10 B. 8 C. 5 D. 3 D 课 堂 练 习 2. 若冒泡排序在某一遍加工过程中没有数据交换，则说明数据已经有序， 优化程序段如下： a=[58,36,23,97,77] n=len(a) ; i=1 ; flag=True while i<=4 and flag==True: flag=Flase for j in range(4,i-1,-1): if a[j]>a[j-1]: a[j],a[j-1]=a[j-1],a[j] ; flag=True i+=1 数 ... ... 
