5.3.1冒泡排序思想及程序实现(第五章 数据结构与算法) 课件-2021-2022学年新教材浙教版(2019)高中信息技术选择性必修1

5.3.1 冒泡排序 浙教版新教材(2019)《数据与数据结构》选择性必修1——5.3 冒泡排序 一、排序 温 故 知 新 温 故 知 新 一、排序 ★概念：整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。在排序的过程中，数据元素的值保持不变，但其在序列中的顺序可能会改变。 探索计算机内部如何排序？ 内部数据存储？ 数组 链表 一、排序 一、冒泡排序思想 男生女生身高大比拼 选择6位男生/女生，将男生按照身高顺序从小到大（升序）排序 经典冒泡从后往前冒，以下演示从前往后冒 2 3 4 5 1 0 1 5 0 5 第一遍：比较5次，交换2次 经典冒泡从后往前冒，以下演示从前往后冒 2 3 4 1 0 5 第一遍：比较5次，交换2次 第二遍：比较4次，交换2次 1 4 0 4 经典冒泡从后往前冒，以下演示从前往后冒 2 3 1 0 4 5 第一遍：比较5次，交换2次 第二遍：比较4次，交换2次 3 1 3 0 第三遍：比较3次，交换2次 经典冒泡从后往前冒，以下演示从前往后冒 2 1 0 3 4 5 第一遍：比较5次，交换2次 第二遍：比较4次，交换2次 第三遍：比较3次，交换2次 2 1 2 0 第四遍：比较2次，交换2次 经典冒泡从后往前冒，以下演示从前往后冒 1 0 2 3 4 5 第一遍：比较5次，交换2次 第二遍：比较4次，交换2次 第三遍：比较3次，交换2次 第四遍：比较2次，交换2次 1 0 第五遍：比较1次，交换1次 经典冒泡：从前往后与从后往前，总比较次数和交换次数不变，排序遍数n-1 一、冒泡排序思想 排序遍数是？比较次数？交换次数？ 一、冒泡排序思想 冒泡排序思想总结： ★ 升序：将后数小于前数的两个数进行交换；降序：将后数大于前数的两数进行交换 ★ n个数最多进行 n-1 遍排序 ★ 两数比较的次数为: n*(n-1)/2 ★ 两数交换次数最多为： n*(n-1)/2 课 堂 练 习 1. 有一组10个数据的无序序列，利用冒泡排序算法进行从小到大的排序，需要比较的次数和最多交换的次数，最多需要进行加工的遍数分别为（ ） A. 9，45，9 B. 45，15，9