(25344532781234”64) (25344532)(78123464) V233213304 25)(34)(45)32)(78)(12)34)(64) (2534)(4532)(1278)(6434) (25323445078643412) (1225323434,456478) 合并的时候,两个子数组的下标 indexI、 index2从两端开始处理,向中间推进。由于两 个子数组的两端互相成为另一个数组的“监视哨”,从而不需要检查子序列结束的情况:;只需 要设置计数变量k,共循环 right-left+1次。 另外,需要提醒学生注意:为了保证稳定性,相等时左边优先出序列 算法中“( right-left+1> THRESHOLD)”的判断,使得长度小于阈值的子序列不必要进 行递归归并,采用更适宜处理短序列的插入排序算法,以提高算法的性能 8.总结 内排序是《数据结构与算法》课程训练学生算法思想、创新思维能力、工程实践能力的 重要环节。 除了上述教学注意事项之外。还需要提醒学生注意实际应用。例如,可以根据排序规模 (n的大小)、稳定性要求、待排数组有序状况、排序码的组合情况等来选择合适的排序算 法,或者对这些排序算法进行适当的组合。遵循以下的一些原则: (1)当待排序的关键码序列基本有序时,直接插入排序最快,冒泡排序速度也较快。 (2)归并排序对待排序关键码的初始排列不敏感,故排序速度较稳定。 (3)若待排序的记录个数n较小时,可采用直接插入或直接选择排序 (4)若n较大时,则应采用时间代价为6(nogn)的快速排序、堆排序、归并排序或基 数排序方法。 (5)当n较大,且输入顺序比较随机(即杂乱无序)时,如果没有稳定性要求,则采 用快速排序效果最好。 (6)当n很大且关键码位数较少时,采用静态链的基数排序效果比较好。 参考文献 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—普 通高等教育“十一五”国家级规划教材 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pku.educn/pkujpk/course/sjjg/(25 34 45 32 78 12 34’ 64) (25 34 45 32)(78 12 34’ 64) (25 34)(45 32)(78 12)(34’ 64) (25)(34)(45)(32)(78)(12)(34’)(64) (25 34)(45 32)(12 78)(64 34’) (25 32 34 45)(78 64 34’ 12 ) (12 25 32 34 34’ 45 64 78) 先 划 分 再 归 并 合并的时候，两个子数组的下标 index1、index2 从两端开始处理，向中间推进。由于两 个子数组的两端互相成为另一个数组的“监视哨”，从而不需要检查子序列结束的情况；只需 要设置计数变量 k，共循环 right-left+1 次。 另外，需要提醒学生注意：为了保证稳定性，相等时左边优先出序列。 算法中“(right-left+1 > THRESHOLD)”的判断，使得长度小于阈值的子序列不必要进 行递归归并，采用更适宜处理短序列的插入排序算法，以提高算法的性能。 8．总结 内排序是《数据结构与算法》课程训练学生算法思想、创新思维能力、工程实践能力的 重要环节。 除了上述教学注意事项之外。还需要提醒学生注意实际应用。例如，可以根据排序规模 （n 的大小）、稳定性要求、待排数组有序状况、排序码的组合情况等来选择合适的排序算 法，或者对这些排序算法进行适当的组合。遵循以下的一些原则： （1）当待排序的关键码序列基本有序时，直接插入排序最快，冒泡排序速度也较快。 （2）归并排序对待排序关键码的初始排列不敏感，故排序速度较稳定。 （3）若待排序的记录个数 n 较小时，可采用直接插入或直接选择排序。 （4）若 n 较大时，则应采用时间代价为 Θ(nlogn)的快速排序、堆排序、归并排序或基 数排序方法。 （5）当 n 较大，且输入顺序比较随机（即杂乱无序）时，如果没有稳定性要求，则采 用快速排序效果最好。 （6）当 n 很大且关键码位数较少时，采用静态链的基数排序效果比较好。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/