对于短序列,直接插入排序比较有效 Shell排序有效地利用了直接插入排序的这两个性质,She排序的需要重点讲解分区及 子序列排序,尤其要注意子序列下标的正确定位。 快速排序、归并排序也经常采用插入排序来优化短序列处理。归并排序还采用了 Sedgwick逆转第2个子序列的优化策略。可以说,插入排序是非常基础而重要的排序算法。 (4)快速排序 快速排序首先从待排序序列中任意选择一个记录作为轴值,然后将剩余的记录分割成比 轴值小的左子序列和比轴值大的右子序列。原问题分解为两个规模更小的同结构子问题,递 归地进行快速排序 快速排序的轴值选择非常重要,应该尽量均匀地划分子序列。快速排序的核心是分区的 过程。快速排序有很多优化策略。 快速和归并排序是经典的分治算法,它几乎是最快的排序算法,得到了广泛的应用,被 评选为20世纪十大算法之一。这也是IT企业常用的应聘考试测试题之一。 5)桶式排序的计数和从序列尾分配的方法 桶式排序扫描一遍序列进行统计计数,然后再统计小于等于编号i的个数,给各桶预留 适当的空间。从序列尾部往前再一次扫描,将具有相同值的记录都分配到同一个桶中。为了 保证稳定性,最后依次按照编号从桶中取出记录,组成一个有序序列。 (7)各种排序算法的稳定性和时间复杂度 时间代价在排序算法中居于非常重要的地位,它是衡量排序算法的最重要的指标。根据 应用需要,可以分别考察最小、平均、最大时间代价。对于记录比较大的情况,可以采取减 少移动记录的策略,例如索引排序法 直接插入、直接选择、冒泡这三种排序算法时间代价都很大,在平均和最差情况下的时 间代价均为On)。三者之中,插入排序的试验时间最好,而冒泡排序的性能最差。因此 插入排序经常被用来与其他排序方法结合使用。 快速排序、归并排序、堆排序、基数排序都是θ(nlogη)量级的排序。快速排序的确是 最快的,比同级别的排序算法都要快一些,尤其是数组规模较大时更为明显。因此,快速排 序在实践中应用十分广泛。 空间代价考虑排序算法所需要的额外空间,包括编译栈消耗的辅助记录空间。直接插入 排序、直接选择排序、冒泡排序、Shel排序、堆排序的空间代价为(1),快速排序的空间 代价为e(logn),归并排序的空间代价为6(m,桶式排序的空间代价为en+m),基数排序的 空间代价为θn+r)。如果有特殊的空间限制,那么要注意采用辅助空间较小的算法。 6.课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向,设计验证型、探索型、综合 应用型的习题和上级题,帮助学生更好地掌握排序算法的基本原理,训练学生的创新思维能 力训练、工程实践能力 内排序可以安排6-8道书面作业,1-2道综合上机实习题。安排一次习题讲评 采用 ACM/ICPC程序竞赛题库POJ系统进行经典算法和验证型、小规模设计型实习训 练。例如,下面是两道ACM排序题目 http:/acm.pku.edu.cn/judgeonline/problem?id=2377对于短序列，直接插入排序比较有效。 Shell 排序有效地利用了直接插入排序的这两个性质，Shell 排序的需要重点讲解分区及 子序列排序，尤其要注意子序列下标的正确定位。 快速排序、归并排序也经常采用插入排序来优化短序列处理。归并排序还采用了 Sedgwick 逆转第 2 个子序列的优化策略。可以说，插入排序是非常基础而重要的排序算法。 （4）快速排序 快速排序首先从待排序序列中任意选择一个记录作为轴值，然后将剩余的记录分割成比 轴值小的左子序列和比轴值大的右子序列。原问题分解为两个规模更小的同结构子问题，递 归地进行快速排序。 快速排序的轴值选择非常重要，应该尽量均匀地划分子序列。快速排序的核心是分区的 过程。快速排序有很多优化策略。 快速和归并排序是经典的分治算法，它几乎是最快的排序算法，得到了广泛的应用，被 评选为 20 世纪十大算法之一。这也是 IT 企业常用的应聘考试测试题之一。 （5）桶式排序的计数和从序列尾分配的方法 桶式排序扫描一遍序列进行统计计数，然后再统计小于等于编号 i 的个数，给各桶预留 适当的空间。从序列尾部往前再一次扫描，将具有相同值的记录都分配到同一个桶中。为了 保证稳定性，最后依次按照编号从桶中取出记录，组成一个有序序列。 （7）各种排序算法的稳定性和时间复杂度 时间代价在排序算法中居于非常重要的地位，它是衡量排序算法的最重要的指标。根据 应用需要，可以分别考察最小、平均、最大时间代价。对于记录比较大的情况，可以采取减 少移动记录的策略，例如索引排序法。 直接插入、直接选择、冒泡这三种排序算法时间代价都很大，在平均和最差情况下的时 间代价均为 Θ(n 2 )。三者之中，插入排序的试验时间最好，而冒泡排序的性能最差。因此， 插入排序经常被用来与其他排序方法结合使用。 快速排序、归并排序、堆排序、基数排序都是 Θ(nlogn)量级的排序。快速排序的确是 最快的，比同级别的排序算法都要快一些，尤其是数组规模较大时更为明显。因此，快速排 序在实践中应用十分广泛。 空间代价考虑排序算法所需要的额外空间，包括编译栈消耗的辅助记录空间。直接插入 排序、直接选择排序、冒泡排序、Shell 排序、堆排序的空间代价为 Θ(1)，快速排序的空间 代价为 Θ(logn)，归并排序的空间代价为 Θ(n)，桶式排序的空间代价为 Θ(n+m)，基数排序的 空间代价为 Θ(n+r)。如果有特殊的空间限制，那么要注意采用辅助空间较小的算法。 6．课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向，设计验证型、探索型、综合 应用型的习题和上级题，帮助学生更好地掌握排序算法的基本原理，训练学生的创新思维能 力训练、工程实践能力。 内排序可以安排 6-8 道书面作业，1-2 道综合上机实习题。安排一次习题讲评。 采用 ACM/ICPC 程序竞赛题库 POJ 系统进行经典算法和验证型、小规模设计型实习训 练。例如，下面是两道 ACM 排序题目： http://acm.pku.edu.cn/JudgeOnline/problem?id=2377