排序算法的时间代价 0.5小时 内排序知识点和应用总结0.5小时 4.重点和难点 内排序重点如下 (1)稳定性 (2)比较和移动运算 (3)插入排序 (4)快速排序 (5)基数排序 内排序难点如下 (1) Shell排序的分区及子序列排序 (2)快速排序 (3)归并排序的优化 (4)桶式排序的计数和从序列尾分配的方法 (5)各种排序算法的稳定性和时间复杂度 5.投授课提示 开展硏究型教学,挖掘知识背后的内容,通过提出问题、探讨方法、研究思想、比较性 能,培养学生的创新意识、创新能力。 下面是内排序的重点和难点内容的讲授注意事项 (1)“稳定性” 如果存在多个具有相同排序码的记录,经过排序后这些记录的相对次序仍然保持不变 这种排序算法称为“稳定的”,否则称为“不稳定的 插入排序、冒泡排序、归并排序、桶排序、基数排序是稳定的排序算法,这些算法基本 上都是逐个处理数据,纪录交换跨度小。 Shell排序、选择排序、堆排序、快速排序,由于 纪录交换的跨度大,而影响了稳定性。 有些排序应用要求算法具有稳定性。基数排序的第二趟以后的排序算法,也必须是稳定 学生最不容易理解的是“选择排序不稳定”这个事实。教师需要举例予以说明。 (2)比较和移动运算 排序算法的时间代价一般通过记录的总比较和总移动次数来衡量,一次移动就是一次记 录赋值,一次swap交换为三次移动。记录的数量、排序码和记录的大小以及输入记录的原 始有序程度,这些都会影响到排序算法的相对运行时间。一般而言,排序算法时间代价主要 是根据比较和移动次数来估价的。 学生容易混淆“移动”和“交换”次数。注意,这里的“移动”和“交换”都是指纪录 的操作。在插入排序等算法中,待排码被存入临时变量,以及最后落位,这样的赋值运算容 易被疏忽。计数变量i+等操作,在排序算法时间代价分析中基本上忽略不计。 3)插入排序和Shel排序 直接插入排序的两个性质:在最好情况(序列本身已是有序的)下时间代价为O(n)排序算法的时间代价 0.5 小时 内排序知识点和应用总结 0.5 小时 4．重点和难点 内排序重点如下： （1）稳定性 （2）比较和移动运算 （3）插入排序 （4）快速排序 （5）基数排序 内排序难点如下： （1）Shell 排序的分区及子序列排序 （2）快速排序 （3）归并排序的优化 （4）桶式排序的计数和从序列尾分配的方法 （5）各种排序算法的稳定性和时间复杂度 5．授课提示 开展研究型教学，挖掘知识背后的内容，通过提出问题、探讨方法、研究思想、比较性 能，培养学生的创新意识、创新能力。 下面是内排序的重点和难点内容的讲授注意事项。 （1）“稳定性” 如果存在多个具有相同排序码的记录，经过排序后这些记录的相对次序仍然保持不变， 这种排序算法称为“稳定的”，否则称为“不稳定的”。 插入排序、冒泡排序、归并排序、桶排序、基数排序是稳定的排序算法，这些算法基本 上都是逐个处理数据，纪录交换跨度小。Shell 排序、选择排序、堆排序、快速排序，由于 纪录交换的跨度大，而影响了稳定性。 有些排序应用要求算法具有稳定性。基数排序的第二趟以后的排序算法，也必须是稳定 的。 学生最不容易理解的是“选择排序不稳定”这个事实。教师需要举例予以说明。 （2）比较和移动运算 排序算法的时间代价一般通过记录的总比较和总移动次数来衡量，一次移动就是一次记 录赋值，一次 swap 交换为三次移动。记录的数量、排序码和记录的大小以及输入记录的原 始有序程度，这些都会影响到排序算法的相对运行时间。一般而言，排序算法时间代价主要 是根据比较和移动次数来估价的。 学生容易混淆“移动”和“交换”次数。注意，这里的“移动”和“交换”都是指纪录 的操作。在插入排序等算法中，待排码被存入临时变量，以及最后落位，这样的赋值运算容 易被疏忽。计数变量 i++等操作，在排序算法时间代价分析中基本上忽略不计。 （3）插入排序和 Shell 排序 直接插入排序的两个性质：在最好情况（序列本身已是有序的）下时间代价为Θ (n)；