数据结构与算法“内排序”教学设计 北京大学信息科学技术学院张铭 1.内排序在课程中的定位和前测知识点 排序是计算机数据处理中经常用到的核心运算,是“数据结构与算法”课程讨论的重点 内容。排序算法最能够体现算法设计和算法分析的魅力,它的算法速度要求非常高,排序主 要分为两类:内排序和外排序。若待排序的记录个数较少,整个排序过程中都在内存进行的 排序叫做内排序。如果内存无法容纳所有待排序记录需要借助于外存,则要尽量减少访外操 作,以提高排序速度,这样的排序叫做外排序。 本章讨论的内排序,主要考虑的是怎样在不同的空间限制下、从不同的角度、采用不同 的策略减少关键码之间的比较次数和记录移动次数来提高排序速度。主要介绍几种比较经典 而又常用的内排序算法,希望学生能掌握排序算法思想、进行代价分析,并学会实验性能比 较方法。根据数据分布特点和处理要求,编写合适的排序算法 前测知识点要求如下,可以根据需要给学生补充 (1)序列的逆置、逆置数概念 (2)swap操作交换两个元素 (3)随机数、随机序列;swap操作交换两个元素 (4)建堆、堆调整过程: (5)判定树概念。 2.学习目标 (1)理解内排序的基本概念,熟练掌握各种主要排序算法 (2)能比较各种排序算法的优缺点,比较他们在最坏、最好、平均情况下的复杂度: (3)能够根据不同的实际情况,选择最合适的排序算法; (4)能够判断排序算法是否稳定 (5)对各种排序算法,能够画出它的判定树。 3.知识点和学时分配 理论授课6学时,建议安排实验12学时。 以下内容是本课程要求的基本教学内容,主讲教师可以根据学生的状况、教师的科研背 景等在某些方面进行扩展和对学生进行引导,以扩大适当学生的涉猎面。对于非计算机类的 学生,可以不讲索引排序和排序算法的时间代价。 各知识点建议授课时间如下 排序问题的基本概念 0.5小时 插入排序(Shel排序)0.5小时 选择排序(堆排序 1小时 交换排序(冒泡、快速)1小时 归并排序 1小时 分配排序和索引排序1小时数据结构与算法“内排序”教学设计 北京大学信息科学技术学院 张铭 1. 内排序在课程中的定位和前测知识点 排序是计算机数据处理中经常用到的核心运算，是“数据结构与算法”课程讨论的重点 内容。排序算法最能够体现算法设计和算法分析的魅力，它的算法速度要求非常高，排序主 要分为两类：内排序和外排序。若待排序的记录个数较少，整个排序过程中都在内存进行的 排序叫做内排序。如果内存无法容纳所有待排序记录需要借助于外存，则要尽量减少访外操 作，以提高排序速度，这样的排序叫做外排序。 本章讨论的内排序，主要考虑的是怎样在不同的空间限制下、从不同的角度、采用不同 的策略减少关键码之间的比较次数和记录移动次数来提高排序速度。主要介绍几种比较经典 而又常用的内排序算法，希望学生能掌握排序算法思想、进行代价分析，并学会实验性能比 较方法。根据数据分布特点和处理要求，编写合适的排序算法。 前测知识点要求如下，可以根据需要给学生补充： （1）序列的逆置、逆置数概念； （2）swap 操作交换两个元素； （3）随机数、随机序列；swap 操作交换两个元素； （4）建堆、堆调整过程； （5）判定树概念。 2．学习目标 （1）理解内排序的基本概念，熟练掌握各种主要排序算法； （2）能比较各种排序算法的优缺点，比较他们在最坏、最好、平均情况下的复杂度； （3）能够根据不同的实际情况，选择最合适的排序算法； （4）能够判断排序算法是否稳定； （5）对各种排序算法，能够画出它的判定树。 3. 知识点和学时分配 理论授课 6 学时，建议安排实验 12 学时。 以下内容是本课程要求的基本教学内容，主讲教师可以根据学生的状况、教师的科研背 景等在某些方面进行扩展和对学生进行引导，以扩大适当学生的涉猎面。对于非计算机类的 学生，可以不讲索引排序和排序算法的时间代价。 各知识点建议授课时间如下： 排序问题的基本概念 0.5 小时 插入排序（Shell 排序） 0.5 小时 选择排序（堆排序） 1 小时 交换排序（冒泡、快速） 1 小时 归并排序 1 小时 分配排序和索引排序 1 小时