【课件】数据排序浙教版（2019）高中信息技术选修1.pptx
知识回顾迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程。f1=1f2=1i=3while i=12:f=f1+f2 f1=f2 f2=f i+=1print(f第i-1月共有f对兔子“)迭代算法处理问题：1.确定迭代变量：由旧值递推出新值的变量；2.建立迭代关系式：从变量的前值推出下个值的公式；3.控制迭代条件：经过若干次重复执行后能够结束。知识回顾递归算法：在计算机科学中，指一种通过重复将问题分解为同类的子问题而解决问题的方法，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。核心思想：把大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，规模较小的又转化为规模更小的问题求解，当问题小到一定程度时，可以直接得出它的解，从而回归求解问题原来的解。即“大事化小，小事化了”的思想。实现条件：1、每一步解决问题的方法有一致的规律：递归公式 2、可以达到某个边界条件：递归出口冒 泡 排 序 算法思想 程序实现冒泡排序Maopao paixu算法思想冒泡排序Maopao paixu算法思想l 是一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。三 要 素l 趟数：n个数最多排 趟就完全有序l 方向：从前往后、从后往前l 升降：升序、降序n-1冒泡排序Maopao paixu算法实践原始数据 170 176 165 183 162比较次数交换次数第一趟排序第二趟排序第三趟排序第四趟排序170 165 176 162 183 4 2165 170 162 176 183 3 2165 162 170 176 183 2 1162 165 170 176 183 1 14+3+2+1=10 2+2+1+1=6总比较次数：总交换次数：冒泡排序Maopao paixu算法实践原始数据170 176 165 183 162比较次数交换次数第一趟第二趟第三趟第四趟原始数据170 176 165 183 162比较次数交换次数第一趟第二趟第三趟第四趟原始数据170 176 165 183 162比较次数交换次数第一趟第二趟第三趟第四趟原始数据170 176 165 183 162比较次数交换次数第一趟第二趟第三趟第四趟从前往后升序从前往后降序从后往前升序从后往前降序170 165 176 162 183 4 2165 170 162 176 183 3 2165 162 170 176 183 2 1162 165 170 176 183 1 1176 170 183 165 162 4 2176 183 170 165 162 3 1183 176 170 165 162 2 1183 176 170 165 162 1 0162 170 176 165 183 4 4162 165 170 176 183 3 2162 165 170 176 183 2 0162 165 170 176 183 1 0183 170 176 165 162 4 3183 176 170 165 162 3 1183 176 170 165 162 2 0183 176 170 165 162 1 0练一练有一组数为：6，2，9，8，7，4，经过一趟冒泡排序后的序列为：2，6，4，9，8，7，第二趟排序后的序列是（）A.2,6,7,4,8,9 B.2,6,4,7,8,9C.2,4,6,7,9,8 D.2,4,6,7,8,9C冒泡排序Maopao paixu程序实现从前往后的升序for j in range(_):If _:for i in range(_):temp=ajaj=aj+1aj+1=tempajaj+1如果符合条件，实现相邻两数交换每一趟升降的控制当后者比前者小(升序)每一趟比较方向及次数的控制处理的趟数的控制1,n0,n-i冒泡排序Maopao paixu程序变式从前往后的降序？for j in range(_):If _:for i in range(_):temp=ajaj=aj+1aj+1=tempajaj+1如果符合条件，实现相邻两数交换每一趟升降的控制当后者比前者小(升序)每一趟比较方向及次数的控制处理的趟数的控制1,n0,n-iajaj+1练一练有如下一段代码a=6,2,8,4,3,7length=len(a)for i in range(1,length):for j in range(0,length-i):if ajaj+1:temp=aj aj=aj+1 aj+1=tempprint(a)Q1:这段代码实现的是冒泡排序算法，根据代码可知排序（选填：从前往后或从后往前）的（选填：升序/降序）。Q2:代码运行结果为。其中第二趟排序结果为。从前往后升序2,3,4,6,7,82,4,3,6,7,8冒泡排序Maopao paixu自定义函数的使用对于需要重复调用的冒泡排序算法，我们可以创建自定义函数bubble_sort()来实现def bubble_sort(a):n=len(a)for i in range(1,n):for j in range(0,n-i):if ajaj+1:temp=aj aj=aj+1 aj+1=temp使用方法：a=3,1,9,7,6bubble_sort(a)print(a)运行结果：1,3,6,7,9练一练运行以下Python程序段后，输出的列表为()def bubble_sort(L)：lengthlen(L)for i in range(1，3)：for j in range(length，i，1)：if LjLj1：tempLj LjLj1 Lj1tempa6，8，2，4，3，7bubble_sort(a)print(a)A.2，3，4，6，7，8 B.8，7，6，4，3，2C.2，3，4，6，8，7 D.2，3，6，8，4，7D冒泡排序Maopao paixu冒泡排序的程序优化优化：观察排序过程，可以发现第三趟冒泡排序后数组已经有序，后面两趟排序实际上没有做任何交换操作，因此可以设置一个标记变量flag来标记某趟排序过程中是否发生了交换。若无交换操作，表示已经完成排序，退出循环。def bubble_sort(a):n=len(a)flag=False for i in range(1,n):for j in range(0,n-i):if ajaj+1:temp=aj aj=aj+1 aj+1=temp flag=True if not flag:break return a
