微项目4 用排序算法进行数据整理

微项目4 用排序算法进行数据整理 学习目标 1、了解计算机排序的方法 2、了解冒泡排序的基本过程 3、掌握用冒泡排序整理数据 4、学会用冒泡排序的思想找到解决实际问题的方法 给下面的动物排顺序 认识排序 排序是把一个任意序列的数据元素排列成按照某关键字的一个有序序列的过程 冒泡排序 案例 站队形 体育课上，老师需要大家从高到低站一排。集合的时候大家随便凑了一排。一共5个人（海绵宝宝、小蜗、派大星、章鱼哥、蟹老板），但是高矮不齐。这时老师说:“我给你们排队的规则，两两比较，矮个靠右站。按照我的办法，你们自己排列队形。”就这样，同学们换来换去，完成了队列的排列 问题:同学们如何根据排队规则，从高到低的顺序站队形? 如何一步步实现排序 什么时候结束排序 案例 站队形 1.从第一个同学开始，如果前一个同学比后一个同学个子矮了，就交换位置，否则不动。 2.第二个再和第三个同学比较，依次类推，直到最后一个同学没人比较了，他是最矮的，依次排序完毕。 3.排除已确定的同学，重复步骤1和2，每次越来越少的同学进行比较换位。 4.直到需要比较的同学剩一个了，就无需比较，队列已经是由高往低依次排列了。 这种站队形的排序方法就是冒泡排序。 冒泡排序，就是从初始位置开始，每次对相邻两个数据进行比较，如顺序无误保持位置不变；顺序错误则交换顺序，不断进行下一次比较，直至数据顺序调整完毕。 鱼吐泡泡 冒泡排序过程就像鱼在水里冒泡的过程，小泡泡在下面，大泡泡在上面 2 5 9 1 3 5 3 2 9 1 冒泡排序的执行过程 以对7、9、5、6、4从小到大为例，进行冒泡升序排序分析 原始数据 7 9 5 6 4 第一次比较后 7 9 5 6 4 第二次比较后 7 5 9 6 4 7 5 6 9 4 7 5 6 4 9 第三次比较后 第四次比较后 第一轮比较 第一轮排序完数据 7 5 6 4 9 第一次比较后 5 7 6 4 9 第二次比较后 5 6 7 4 9 5 6 4 7 9 第三次比较后 第二轮比较 第二轮排序完数据 第一次比较后 5 6 4 7 9 第二次比较后 5 4 6 7 9 5 6 4 7 9 第三轮比较 第三轮排序完数据 第一次比较后 4 5 6 7 9 5 4 6 7 9 第四轮比较 5个数据进行冒泡排序 一共执行了4轮 第一轮比较了4次 第二轮比较了3次 第三轮比较了2次 第四轮比较了1次 思考：那n个数据元素进行冒泡排序是什么规律？ n个数据进行冒泡排序 一共执行n-1轮 第一轮比较n-1次 第二轮比较n-2次 第三轮比较n-3次 第K轮比较n-k次 冒泡排序升序口诀： n个数字来比较 两两比较小靠前 比较轮数n-1 每轮次数n-k 有一组10个数据的无序序列，利用冒泡排序算法进行从小到大的排序，需要比较的次数和最多交换的次数，最多需要进行加工的轮数分别为（ ） 9，45，9 B. 45，15，9 C.45，45，9 D.15，45，8 C 2.通过“冒泡排序”的算法，我们得到12、-3、4、8、-5这5个数第2轮排序后的结果为( ) -3、4、8、-5、12 -3、4、-5、8、12 C. -3、-5、4、8、12 D. -5、-3、4、8、12 B 3.采用冒泡排序算法对数据序列“2，3，4，5，1，0”完成升序排序，则需要交换的次数为（ ） A.9次 B.12次 C.15次 D.18次 A 4.采用冒泡排序算法对数据序列“1,7,2,5,12,15,27,10,6,30”完成升序排序，理论上讲共需进行排序的轮数为（ ） A.5遍 B.6遍 C.7遍 D.8遍 A 冒泡排序 如果待排序的数据量达到上万、上百万，甚至更大，如何快速地利用冒泡排序来解决问题 人工排序 电脑排序 冒泡排序算法+计算机 冒泡排序算法分析 相邻元素比较、逆序交换 从第一个元素到最后一个元素 多轮排序 分支结构 循环结构 循环结构 算法： 循环列举第一个元素到最后一个元素： 循环进行下列步骤： 直到所有元素有序排列，程序结束 如果相邻两个元素满足大小条件： 交换相邻两个逆序元素的位置 冒泡排序解决问题的一般步骤 分析问题 设计算法 确定排序对象 确定交换条件 排序结束条件 循环与分支结构 程序实现 运行程序 编写代码 得到有序序列 python程序 课堂总结 相邻元素两两比较、逆序交换、多轮排序 每轮排序过程中，值小的元素向前移动，值大的元素向后移动