5.3数据排序_冒泡课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第五章浙教版（2019）

数据排序 – 冒泡排序（升序为例） 信息技术 选考课程 排序 排序（sorting）就是整理数据的序列，使其中元素按照递增（或递减）的次序重新排列的操作 两种待排序数据的存储方式： 数组存储：排序过程是对数据本身进行物理重排，改变其存储位置； 链表存储：无须移动数据，仅修改指针即可； 常见的排序算法：冒泡排序 选择排序、插入排序、快速排序、桶排序、堆排序、归并排序等 冒泡排序基本思想：在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上浮）”，较小的数“上浮（下沉）”的一种排序技术。 冒泡排序过程 (从后往前扫描 小数上浮) i：记录排序趟次 j：记录每次比较的数组元素下标(不能下标越界) 相邻元素比较：后一个和前一个，即a[j]和a[j-1] i=0 '第一趟 for j in range( ? , ? ,-1):#从后往前扫描 if a[j-1] ? a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 i=0 '第一趟 for j in range(5,0,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 冒泡排序过程 (从后往前扫描 小数上浮) i：记录排序趟次 j：记录每次比较的数组元素下标(不能下标越界) 相邻元素比较：后一个和前一个，即a[j]和a[j-1] i=1 '第二趟 for j in range(5,1,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 i=1 '第二趟 for j in range( ? , ? ,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 冒泡排序过程 (从后往前扫描 小数上浮) i：记录排序趟次 j：记录每次比较的数组元素下标(不能下标越界) 相邻元素比较：后一个和前一个，即a[j]和a[j-1] i=2 '第三趟 for j in range(5,2,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 冒泡排序过程 (从后往前扫描 小数上浮) i：记录排序趟次 j：记录每次比较的数组元素下标(不能下标越界) 相邻元素比较：后一个和前一个，即即a[j]和a[j-1] i=3 '第四趟 for j in range(5,3,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 a[j],a[j-1] = a[j-1],a[j] #交换 冒泡排序过程 (从后往前扫描 小数上浮) i：记录排序趟次 j：记录每次比较的数组元素下标(不能下标越界) 相邻元素比较：后一个和前一个，即a[j]和a[j-1] i=4 '第五趟 for j in range(5,4,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 经典冒泡排序的比较总次数： 第一趟排序需进行 n - 1 次比较，第二趟排序需进行 n - 2 次比较，以此类推，共需要比较次数是(n–1)+(n–2) + … +2+1 = n*(n–1)/2 比较次数 (n*n-n)/2 交换次数 逆序对数量 排序遍数 n-1 三、冒泡排序程序实现(从后往前 小数上浮) i=0 '第一趟 for j in range(5,0,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 i=1 '第二趟 for j in range(5,1,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 i=2 '第三趟 for j in range(5,2,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 i=3 '第四趟 for j in range(5,3,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 a[j],a[j-1] = a[j-1],a[j] #交换 i=4 '第五趟 for j in range(5,4,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j] #交换 n=len(a) for i in range(___,____): for j in range(____,____,____): if a[j-1] ____ a[j] : a[j],a[j-1] = a[j-1],a[j] #交换 0 n-1 n-1 i -1 > IDLE实现下 8 三、冒泡排序程序实现(以升序为例) def bubble_sort(a): n = len(a) for i in range(0,n-1):#排序趟数 for j in range(n-1,i,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j]#交换 外循环用来控制排序趟次（或待排序区间左边界），内循环用来扫描待排序区间，将相邻的较小值向左冒泡，从而达到将最小值冒泡到最左端的效果。 内外两层循环分别起什么作用？或者说变量i和j的含义分别是什么？ 问题来了：从前往后扫描可以吗？那比较的仍然是a[j-1] 和a[j]吗？ IDLE实现下 9 冒泡排序过程 (从前往后扫描 大数下沉) i：记录排序趟次 j：记录每次比较的数组元素下标(不能下标越界) 相邻元素比较：前一个和后一个，即a[j]和a[j+1] i=5 '第一趟 for j in range( ? , ? ,1):#从前往后扫描 if a[j] ? a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 i=5 '第一趟 for j in range(0,5,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 冒泡排序过程 (从前往后扫描 大数下沉) i：记录排序趟次 j：记录每次比较的数组元素下标(不能下标越界) 相邻元素比较：前一个和后一个，即a[j]和a[j+1] i=4 '第二趟 for j in range( ? , ? ,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 i=4 '第二趟 for j in range(0,4,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 其他趟以此类推.... 三、冒泡排序程序实现(从前往后 大数下沉) i=5 '第一趟 for j in range(0,5,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 i=4 '第二趟 for j in range(0,4,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 i=3 '第三趟 for j in range(0,3,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 i=2 '第四趟 for j in range(0,2,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 i=1 '第五趟 for j in range(0,1,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j] #交换 n=len(a) for i in range(____,____): for j in range(____,____,____):#从前往后扫描 if a[j] ____ a[j+1] : #升序 a[j],a[j+1] = a[j+1],a[j] #交换 n-1 0,-1 0 i 1 > IDLE实现下 12 三、冒泡排序程序实现(以升序为例) def bubble_sort(a): n = len(a) for i in range(n-1,0,-1):#排序趟数 for j in range(0,i,1):#从前往后扫描 if a[j] > a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j]#交换 外循环用来控制排序趟次（或待排序区间右边界），内循环用来扫描待排序区间，将相邻的较大值向右冒泡，从而达到将最大值冒泡到最右端的效果。 IDLE实现下 13 三、程序实现对比小结 def bubble_sort(a): n = len(a) # n=5 for i in range(n-1,0,-1):#排序趟数 for j in range(0,i):#从前往后扫描 if a[j]> a[j+1] : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j]#交换 def bubble_sort(a): n = len(a) # n=5 for i in range(0,n-1):#排序趟数 for j in range(n-1,i,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j]#交换 注意三个蓝框的位置是解题的突破口 IDLE实现下 14 三、程序实现填空版--请同学们填空 def bubble_sort(a): n = len(a) for i in range(____,___,___):#排序趟数 for j in range(____,______):#从前往后扫描 if _______> ________ : #升序 大数下沉 a[j],a[j+1] = a[j+1],a[j]#交换 def bubble_sort(a): n = len(a) for i in range(____,____):#排序趟数 for j in range(____,___,___):#从后往前扫描 if ______> _____ : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j]#交换 温馨提示：这两段核心代码要会能默写 0 n-1 n-1 i -1 a[ j-1 ] a[ j ] n-1 0 -1 0 i a[ j ] a[ j+1 ] IDLE实现下 15 1、已知数组a的初始值为[5,9,3,8,1,2]，采用冒泡排序算法对其进行从小到大排序，已知第一趟排序后，数组a的值变成[1,5,9,3,8,2]，请写出每一趟排序后数组a的值。[绿本P59例1] 第1趟：[1,5,9,3,8,2] 第2趟：[1,2,5,9,3,8] 第3趟：[1,2,3,5,9,8] 第4趟：[1,2,3,5,8,9] 第5趟：[1,2,3,5,8,9] 随堂练习 2、5个学生的身高依次为172,177,180,168,165，采用冒泡排序对这5个学生的身高数据进行从低到高排序，总共需要比较的次数为（ ） A.4 B.5 C.10 D.20 C 3、5个学生的身高依次为172,177,180,168,165，采用冒泡排序对这5个学生的身高数据进行从低到高排序，总共需要交换的次数为（ ） A.6 B.7 C.8 D.10 B 随堂练习 随堂练习 4、若采用冒泡排序对数据46,33,87,15,45,29进行排序处理，排序过程如下表所示。则第二遍加工后的结果是（ ） 原始数据 46 33 87 15 45 29 第一遍加工后 15 46 33 87 29 45 第二遍加工后 第三遍加工后 15 29 33 46 45 87 …… [15,46,29,33,87,45] B. [15,29,46,33,87,45] C. [15,29,33,46,87,45] D. [15,29,33,46,45,87] B 18 随堂练习 5、对6个数据采用冒泡排序算法进行降序排序，第一遍加工后的结果如下表所示。 原始数据 第一遍加工后 69 46 24 18 57 32 …… 原始数据可能是（ ） [46,69,18,57,24,32] B. [46,24,57,18,69,32] C. [46,24,18,69,57,32] D. [46,24,69,18,57,32] C 6、对6个数据采用冒泡排序算法进行降序排序，第一遍加工后的结果如下表所示。 原始数据 第一遍加工后 46 69 24 57 32 18 …… 原始数据可能是（ ） [46,69,18,57,24,32] B. [46,24,57,18,69,32] C. [46,24,18,69,57,32] D. [46,24,69,18,57,32] D 随堂练习 7、已知字符串数组a的原始数据为["128","26","9","61","15","2","318"]，为了对该数组进行排序操作，小美编写了如下Python程序：[作业本P165第5题] for i in range(3): for j in range(6,i+1,-1): if a[j]<a[j-1]: a[j],a[j-1]=a[j-1],a[j] A、["128","15","2","26","318","61","9"] B、["128","15","26","9","61","2","318"] C、["128","15","2","26","9","61","318"] D、["128","15","2","26","318","9","61"] D 随堂练习 8、某Python程序如下：[绿本P59例2] a=[3,1,9,7,6,3] n=len(a) for i in range(1,n): for j in range(n-2,i-2,-1): if a[j]<a[j+1]: a[j],a[j+1]=a[j+1],a[j] A、[9,3,1,7,6,3] B、[9,7,6,3,3,1] C、[1,3,3,9,7,6] D、[1,3,3,6,7,9] B 9、有如下程序段： for i in range(9): for j in range(9,i+1,-1): if a[j]<a[j-2]: a[j],a[j-2]=a[j-2],a[j] 数组a[0]到a[9]的值依次为：“3,17,2,14,15,6,7,18,9,4”，执行程序后，数组元素a[7]的值为（ ） A、3 B、4 C、15 D、17 随堂练习 冒泡排序优化--外层优化 优化排序趟数 前面演示的经典冒泡排序测试数据中，对6个元素进行排序，理论上需要进行5轮排序，共比较15次。但实际情况可能出现以上这种情况，到某一轮排序该数组已经有序（没有交换出现），说明可以提前结束排序。 def bubble_sort(a): n = len(a) for i in range(0,n-1):#排序趟数 flag=False #没交换 for j in range(n-1,i,-1):#从后往前扫描 if a[j-1] > a[j] : #升序 小数上浮 a[j],a[j-1] = a[j-1],a[j]#交换 flag=True #有交换 if not flag:#flag=False结束排序 break return a 冒泡排序优化--内层优化 优化待排序区间 对10个数进行排序，理论上需要9轮排序，共比较45次，但实际情况是发现某一遍排序过程中，最后一次交换发生在a[j]和a[j-1]的位置，表示在[0,j-1]的位置不存在逆序对，即剩余元素已经有序，则下一遍排序只需要比较到 j 的位置。 def bubble_sort(a): n = len(a) last = 0 for i in range(0,n-1): for j in range(n-1,last,-1): if a[j]>a[j-1]: #降序 a[j],a[j-1]=a[j-1],a[j] last = j #记录最后一次交换发生下标 冒泡排序优化--双向冒泡排序 每一趟冒泡排序过程中，先从前向后冒泡，将最小值推送到最左端，再从后向前冒泡，将最大值推送到最右端。 def bubble_sort(a): n = len(a) L,R = 0,n-1 while L< R: for j in range(L,R): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] ________ #缩小边界 for j in range(R,L,-1): if a[j]<a[j-1]: a[j],a[j-1]=a[j-1],a[j] ________#缩小边界 R = R - 1 L = L + 1 冒泡去重：剔除重复数据后升序排序 冒泡去重：剔除重复数据后升序排序 a[j-1]>a[j] a[top] a[:top+1] $$