1、选择性必修一数据与数据结构第五章 数据结构与算法5.3.1 排序排序的概念、排序的概念、排序算法的思想算法的思想情境导入在一次电视节目上,谷歌总裁施密特提出问题:“如何才能更有效地对一百万个32位长整数进行排序?”同在现场的奥巴马总统立刻响应道:“肯定不能用冒泡排序法。”施密特评价说:天哪!他是从谁那里听说这个的。”返回什么是排序你能举一些排序的生活例子吗？排序如何进行返回1.数据的组织形式2.数组中的数据排序冒泡排序播放“冒泡排序.gif”冒泡排序的前四遍85951116132523比较比较交换交换交换交换比较比较交换交换比较比较不交换不交换比较比较交换交换比较比较不交换不交换交换交换比较比
2、较交换交换9523161311852585951116132523比较比较交换交换比较比较交换交换比较比较比较比较不交换不交换比较比较不交换不交换25231613119585比较比较比较比较不交换不交换25231613118595比较比较不交换不交换比较比较不交换不交换比较比较不交换不交换比较比较不交换不交换比较比较不交换不交换原始数据一二三四设计算法对于n个元素，第一遍加工将最大元素下沉到第n个位置对 于 剩 下 的n-1元素，反复 使 用 该 规则，直 到 最后 余 下 两 个元 素 进 行 比较和交换冒泡排序完成冒泡排序自然语言描述1.要排序的数有n个，则需要n-1遍加工2.第j遍加工中
3、，从第一个数开始，相邻两数比较，若反序则交换两者的位置；直到第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 15 4 3 2 1掌握理解排序的基本概念5 4 3 2 15 4 3 2 1能够掌握冒泡排序的基本思想与方法5 4 3 2 15 4 3 2 1能进行冒泡排序的时间复杂度的分析，以及对比较次数、交换次数的细致分析。5 4 3 2 15 4 3 2 1课堂作业1.完成课后作业
