常见的排序算法-冒泡排序 课件 2023-2024学年浙教版（2019）高中信息技术选修1

第五章数据结构与算法选修一《数据与数据结构》5.3.2常见的排序算法——冒泡排序排序就是整理数据的序列，使其中元素按照某个值递增（或递减）的次序重新排列的操作。排序是什么？太抽象了，无法理解排序是什么？1891412718914127按数组形式进行存储18914127按链表形式进行存储79121418对数组进行升序排序Python中的排序实现第一种：列表自带的sort算法列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列。第二种：内建函数sorted方法内建函数sorted方法，返回一个新的序列，原来序列依然存在。a=[5,7,6,3,4,1,2]a.sort()print(a) #[1,2,3,4,5,6,7]a=[5,7,6,3,4,1,2]a.sort(reverse=True)print(a) #[7,6,5,4,3,2,1]a=[5,7,6,3,4,1,2]b=sorted(a)print(a) #[5,7,6,3,4,1,2]print(b) #[1,2,3,4,5,6,7]常见的排序算法—冒泡排序冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。18914127p[0]p[1]p[2]p[3]p[4]91814127914181279141218791412718冒泡排序算法对数组p做的第1遍加工常见的排序算法—冒泡排序91412718914127189121471891271418冒泡排序算法对数组p做的第2遍加工冒泡排序算法对数组p做的第3遍加工912714189127141897121418常见的排序算法—冒泡排序9712141879121418冒泡排序算法对数组p做的第4遍加工对长度为5的数组p，一共需要4次加工对长度为n的数组p①一共需要(n-1)次加工②在第i遍加工当中，共需比较(n-i)次

①一共需要(n-1)次加工常见的排序算法—冒泡排序91412718912714189712141879121418排好第1大的元素排好第2大的元素排好第4大的元素排好第3大的元素每一次加工，都是为了排好未排序数据当中最大的元素常见的排序算法—冒泡排序②在第i遍加工当中，共需比较(n-i)次n=5i=1n-i=4排好元素：i-1=0个共有n-(i-1)=5个元素需要比较两两比较需要比较4次常见的排序算法—冒泡排序②在第i遍加工当中，共需比较(n-i)次n=5i=2n-i=3排好元素：i-1=1个共有n-(i-1)=4个元素需要比较两两比较需要比较3次常见的排序算法—冒泡排序②在第i遍加工当中，共需比较(n-i)次n=5i=3n-i=2排好元素：i-1=2个共有n-(i-1)=3个元素需要比较两两比较需要比较2次n=5i=4n-i=1排好元素：i-1=3个共有n-(i-1)=2个元素需要比较两两比较需要比较1次如果说一共有n个元素，第i遍加工当中共有(n-i+1)个元素需要比较两两比较需要比较(n-i)次常见的排序算法—冒泡排序

第1遍加工：比较（n-1）次第2遍加工：比较（n-2）次…第（n-2）遍加工：比较2次第（n-1）遍加工：比较1次①一共需要(n-1)次加工Q：一共需要几次加工？

总共需要比较次数S冒泡排序算法实现自主阅读课本第130页，思考一共需要几个变量？每个变量的作用是什么？i：记录当前正进行的处理遍数j：记录当前数组元素的下标。每遍处理过程中，j总是从第一个数据元素，下标为0开始。按每次加1的方式直至j+1=n-i=>j=n-i-1为止每次比较p[j]与p[j+1]进行比较，若p[j]>p[j+1]，则进行互换i=2j=0j+1j=1j+1j=2j+1j=3j+1i=1i=1i=1i=1j=0j+1j=1j+1j=2j+1i=2i=2i=3i=3i=4j=0j+1j=1j+1j=0j+1每遍处理过程中，j总是从第一个数据元素，下标为0开始。按每次加1的方式直至j+1=n-i=>j=n-i-1为止每次比较p[j]与p[j+1]进行比较，若p[j]>p[j+1]，则进行互换冒泡排序算法实现i：记录当前正进行的处理遍数j：记录当前数组元素的下标。①一共需要(n-1)次加工冒泡排序算法实现Python代码实现defbubble_sort(p):length=len(p)foriinrange(1,length):forjinrange(0,length-i):ifp[j]>p[j+1]:temp=p[j]p[j]=