(
课件网) 选择性必修一《数据与数据结构》 第五章 数据结构与算法 5.3.1 排序的概念、排序算法的思想 情境导入 在一次电视节目上,谷歌总裁施密特提出问题:“如何才能更有效地对一百万个32位长整数进行排序 ”同在现场的奥巴马总统立刻响应道:“肯定不能用冒泡排序法。”施密特评价说:"天哪!他是从谁那里听说这个的。” 返回 什么是排序 你能举一些排序的生活例子吗？ 排序如何进行 返回 1.数据的组织形式 2.数组中的数据排序 冒泡排序 播放“冒泡排序.gif” 冒泡排序的前四遍 85 95 11 16 13 25 23 比较 交换 交换 比较 交换 比较 不交换 比较 交换 比较 不交换 交换 比较 交换 95 23 16 13 11 85 25 85 95 11 16 13 25 23 比较 交换 比较 交换 比较 比较 不交换 比较 不交换 25 23 16 13 11 95 85 比较 比较 不交换 25 23 16 13 11 85 95 比较 不交换 比较 不交换 比较 不交换 比较 不交换 比较 不交换 原始数据 一 二 三 四 设计算法 对于n个元素，第一遍加工将最大元素下沉到第n个位置 对于剩下的n-1元素，反复使用该规则，直到最后余下两个元素进行比较和交换 冒泡排序完成 冒泡排序 自然语言描述 1.要排序的数有n个，则需要n-1遍加工 2.第j遍加工中，从第一个数开始，相邻两数比较，若反序则交换两者的位置；直到第n+1-j个数为止，第一个数与第二个数比较，第二个数与第三个数比较，......，第n-j个与第n+1-j个比较，共比较n-j次。此时第n+1-j个位置上的数已经按要求排好，所以不参加以后的比较和交换操作。 3. 重复第2步n-1遍，结束排序 冒泡排序的时间复杂度 对n个元素的数组，用冒泡法进行排序时，共需比较多少次 小组讨论：为什么奥巴马总统说:“肯定不能用冒泡排序法。” 引入“选择排序”的基本思想与方法。并与冒泡排序相比较，分析为什么奥巴马总统说:“肯定不能用冒泡排序法。” 排序的基本概念 冒泡排序的时间复杂度分析 冒泡排序的基本思想与方法 认识选择排序 课堂小结 学习评价 对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想） 评分项 自我评价 同学互评 能举例说明生活中的排序场景 5 4 3 2 1 5 4 3 2 1 掌握理解排序的基本概念 5 4 3 2 1 5 4 3 2 1 能够掌握冒泡排序的基本思想与方法 5 4 3 2 1 5 4 3 2 1 能进行冒泡排序的时间复杂度的分析，以及对比较次数、交换次数的细致分析。 5 4 3 2 1 5 4 3 2 1 课堂作业 1.完成课后作业
