浙教版 (2019)选修1 数据与数据结构第二章 数据与链表本章综合与测试课文内容课件ppt

这是一份浙教版 (2019)选修1 数据与数据结构第二章 数据与链表本章综合与测试课文内容课件ppt，共15页。PPT课件主要包含了实例分析，排序号，i1第一次排序，算法分析，n-1，i+1，课堂练习等内容，欢迎下载使用。

请将下列数据按从大到小的顺序，利用冒泡法排序
｛30,38,65,97,76,13,27,49}
现将8号数据49和7号数据27比较，因为49>27所以，49和27的位置互换，变为：
j=8:第一步：8号、7号排序
t=d(8) : d(8)=d(7) : d(7)=t
j=7:第二步：7号6号排序
现将7号数据49和6号数据13比较，因为49>13所以，49和13的位置互换，变为：
t=d(7) : d(7)=d(6) : d(6)=t
j=6:第三步：比较6、5号数据
j=5:第四步比较5、4号数据方法同第三步，因为76<97所以数据顺序不变
现将6号数据49和5号数据76比较，因为49<76所以，49和76的位置不互换。
j=4 :第五步：比较4、3号数据
现将4号数据97和3号数据65比较，因为97>65所以，97和65的位置互换。
t=d(4) : d(4)=d(3) : d(3)=t
j=3:第六步：比较3、2号数据：
现将3号数据97和2号数据38比较，因为97>38所以，97和38的位置互换。
t=d(3) : d(3)=d(2) : d(2)=t
j=2 第七步：比较2、1号数据
现将2号数据97和1号数据30比较，因为97>30所以，97和30的位置互换。
t=d(2) : d(2)=d(1) : d(1)=t
这样就完成了第一次排序，它的基本特征是将最大数排到了最左边，然后再从第8个开始，进行第二次排序，将第二大的数据排到了第二位，反复下去，就可以完成排序。一共要进行7次才能完成。
经过第二次排序，数据顺序应该是什么样的？
第1次冒泡排序时(i=1) j 从 8 开始到2
Fr j=8 t 2 step -1 if d(j)第2次冒泡排序时(i=2) j 从 8 开始到3
Fr j=8 t 3 step -1 if d(j)第3次冒泡排序时(i=3) j 从8 开始到4
Fr j=8 t 4 step -1 if d(j)当i 从1到7 变化时 每次 j 从8 到i+1 时 d(j)>d(j-1)时,则交换它们
第4次冒泡排序时(i=4) j 从 8 开始到5
Fr j=8 t 5 step -1 if d(j)第5次冒泡排序时(i=5) j 从 8 开始到6
Fr j=8 t 6 step -1 if d(j)第6次冒泡排序时(i=6) j 从 8 开始到7
Fr j=8 t 7 step -1 if d(j)第7次冒泡排序时(i=7) j 从 8 开始到8
Fr j=8 t 8 step -1 if d(j)1.冒泡法排序完成n个数据的一次排序需要n-1趟比较，完成整个排序需要n*(n-1)/2次比较，对于数据较多时，计算量很大。
2.有些数据的冒泡法排序可能用更少的步骤可以完成，后面的步骤可能毫无意义，但计算机必须完成。
3.交换数据时注意引入第三方变量。
提高：如果要对有n个元素的数组进行排序，那么
要进行________轮冒泡，其中外循环变量i从 到 变化，内循环变量j从 到 变化。
a(1)、a(2)、a(3)、…a(n-2)、a(n-1)、a(n)
数组d（1 t n）Fr i = 1 T n-1 （ i：n个数排序共需进行n-1趟） Fr j = n T i + 1 Step -1 （j ：控制元素对比与交换） if d(j)>d(j-1) then （每一趟从后往前，数据比较） t=d(j) : d(j)=d(j-1) : d(j-1)=t （满足条件，数据交换） Next jNext i
思考：如果以升序进行冒泡排序，划线处的程序代码 如何修改？
今年北京奥运会有七个国家或地区参加，开幕式按照国家或地区英文名从小到大的次序出场，已知这七个国家或地区的名字，请写出经前三趟冒泡后出场的次序表。 England, France , American ， Italy, Japan, China, Hngkng