5.3 数据排序　课件-2022—2023学年浙教版（2019）高中信息技术选修1

知识回顾 迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程。 f1 = 1 f2 = 1 i = 3 while i <= 12: f = f1 + f2 f1 = f2 f2 = f i += 1 print(f"第{i-1}月共有{f}对兔子“) 迭代算法处理问题： 确定迭代变量：由旧值递推出新值的变量； 建立迭代关系式：从变量的前值推出下个值的公式； 控制迭代条件：经过若干次重复执行后能够结束。 1 知识回顾 递归算法：在计算机科学中，指一种通过重复将问题分解为同类的子问题而解决问题的方法，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 核心思想：把大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，规模较小的又转化为规模更小的问题求解，当问题小到一定程度时，可以直接得出它的解，从而回归求解问题原来的解。即“大事化小，小事化了”的思想。 实现条件：1、每一步解决问题的方法有一致的规律：递归公式 2、可以达到某个边界条件：递归出口 2 CHZX 5.3 数据排序 浙江省高中信息技术 选择性必修一 《数据与数据结构》 昌化中学 应彤鑫 3 冒泡排序 算法思想 程序实现 01 4 冒泡排序 Maopao paixu 算法思想 5 冒泡排序 Maopao paixu 算法思想 是一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 三 要 素 趟数：n个数最多排 趟就完全有序 方向：从前往后、从后往前 升降：升序、降序 n-1 6 冒泡排序 Maopao paixu 算法实践 原始数据 170 176 165 183 162 比较次数 交换次数 第一趟 排序 第二趟 排序 第三趟 排序 第四趟 排序 170 165 176 162 183 4 2 165 170 162 176 183 3 2 165 162 170 176 183 2 1 162 165 170 176 183 1 1 4+3+2+1=10 2+2+1+1=6 总比较次数： 总交换次数： 7 冒泡排序 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 2 165 170 162 176 183 3 2 165 162 170 176 183 2 1 162 165 170 176 183 1 1 176 170 183 165 162 4 2 176 183 170 165 162 3 1 183 176 170 165 162 2 1 183 176 170 165 162 1 0 162 170 176 165 183 4 4 162 165 170 176 183 3 2 162 165 170 176 183 2 0 162 165 170 176 183 1 0 183 170 176 165 162 4 3 183 176 170 165 162 3 1 183 176 170 165 162 2 0 183 176 170 165 162 1 0 8 练一练 有一组数为