数据结构与算法“内排序”教学设计 北京大学信息科学技术学院张铭 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 小时
排序算法的时间代价 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)；
对于短序列,直接插入排序比较有效 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 )。三者之中，插入排序的试验时间最好，而冒泡排序的性能最差。因此， 插入排序经常被用来与其他排序方法结合使用。 快速排序、归并排序、堆排序、基数排序都是 Θ(nlogn)量级的排序。快速排序的确是 最快的，比同级别的排序算法都要快一些，尤其是数组规模较大时更为明显。因此，快速排 序在实践中应用十分广泛。 空间代价考虑排序算法所需要的额外空间，包括编译栈消耗的辅助记录空间。直接插入 排序、直接选择排序、冒泡排序、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
http://acm.pku.edu.cn/judgeonline/probleM?id=1649 设计与学科前沿研究相结合的综合实习大项目进行设计型和综合型实践训练,例如让学 生在开源的 Lucene等文本索引包基础上,添加自己的网页排序算法。 7.教学案例 归并排序 Sedgwick逆转第2个子序列的优化策略 算法思想如下:在把数组暂时复制到临时数组时,将第二个子数组中元素的顺序颠倒了 一下。这样,两个子数组从两端开始处理,向中间推进,使得这两个子数组的两端互相成为 另一个数组的“监视哨”,从而不需要检査子序列结束的情况。另外,当子数组小于某个长度 (例如28)时,也不继续递归,而是在最后对整个序列使用插入排序。 算法代码如下: #define THRESHOLd 28 emplate void ModMerge Sort( Record array, Record Temp array, int left, int right){∥Aray为待排序数组,left, right 两端 int middle. if (right-left+1>THRESHOLD) ∥如果序列长度大于阙值(28最佳),递归归并 middle=(left+ right)/2 ∥从中间划分为两个子序列 ModMergesorti(Aray, Temp Array, left, middle),∥对左边一半进行递归 ModMerge Sort(Aray, Temp array, middle+l, right),∥对右边一半进行递归 ModMerge( Array, Temp Array, left, right, middle); 亍归并 else InsertSort(& Array[left], right-lefi+1);,∥小长度子序列进行插入排序,“&”传Amay[e的地址 ∥优化的 Sedgwick两个有序子序列归并,右子序列逆置了,都从两端向中间扫描,归并到新数组 void ModMerge( Record Array[, Record TempArrayll, int left, int right,int middle) H fiE ∥两个子序列的起始位置 int ij, k for(i=left; i<= middle; i++ 制左边的子序列 Temp Array[]= Array[]; forg=1; j<=right-middle, j++) ∥复制右边的子序列,但顺序颠倒过来 Temp Array[right-j+1]= Array[j+middle] ∥开始归并,取较小者插入合并数组中 for(indexI left, index2=right, k= left; k<=right; k++) if( Temp array[ indexI]< TempArray[index2])∥为保证稳定性,相等时左边优先 Array[k]= Temp[index++ else Array[k]=TempArray index2-] 讲解算法时,注意介绍前面的图示。强调复制右边的子序列时,顺序颠倒过来
http://acm.pku.edu.cn/JudgeOnline/problem?id=1649 设计与学科前沿研究相结合的综合实习大项目进行设计型和综合型实践训练，例如让学 生在开源的 Lucene 等文本索引包基础上，添加自己的网页排序算法。 7．教学案例 归并排序 Sedgwick 逆转第 2 个子序列的优化策略。 算法思想如下：在把数组暂时复制到临时数组时，将第二个子数组中元素的顺序颠倒了 一下。这样，两个子数组从两端开始处理，向中间推进，使得这两个子数组的两端互相成为 另一个数组的“监视哨”，从而不需要检查子序列结束的情况。另外，当子数组小于某个长度 （例如 28）时，也不继续递归，而是在最后对整个序列使用插入排序。 算法代码如下： #define THRESHOLD 28 template void ModMergeSort(Record Array[], Record TempArray[], int left, int right) { // Array 为待排序数组，left，right 两端 int middle; if (right-left+1 > THRESHOLD) { // 如果序列长度大于阈值(28 最佳)，递归归并 middle = (left + right) / 2; // 从中间划分为两个子序列 ModMergeSort(Array, TempArray ,left,middle); // 对左边一半进行递归 ModMergeSort(Array, TempArray ,middle+1,right);// 对右边一半进行递归 ModMerge(Array, TempArray ,left,right,middle); // 进行归并 } else InsertSort(&Array[left],right-left+1); // 小长度子序列进行插入排序，“&”传 Array[left]的地址 } // 优化的 Sedgwick 两个有序子序列归并，右子序列逆置了，都从两端向中间扫描，归并到新数组 template void ModMerge(Record Array[],Record TempArray[],int left,int right,int middle) { //归并过程 int index1,index2; // 两个子序列的起始位置 int i,j,k ; for (i = left; i <= middle; i++) // 复制左边的子序列 TempArray[i] = Array[i]; for (j = 1; j <= right-middle; j++) // 复制右边的子序列，但顺序颠倒过来 TempArray[right-j+1] = Array[j+middle]; // 开始归并，取较小者插入合并数组中 for (index1 = left, index2 = right, k = left; k <= right; k++) if (TempArray[index1] <= TempArray[index2]) // 为保证稳定性，相等时左边优先 Array[k] = TempArray[index1++]; else Array[k] = TempArray[index2--]; } 讲解算法时，注意介绍前面的图示。强调复制右边的子序列时，顺序颠倒过来
(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 较大时，则应采用时间代价为 Θ(nlogn)的快速排序、堆排序、归并排序或基 数排序方法。 （5）当 n 较大，且输入顺序比较随机（即杂乱无序）时，如果没有稳定性要求，则采 用快速排序效果最好。 （6）当 n 很大且关键码位数较少时，采用静态链的基数排序效果比较好。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/
4.蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3。 5.张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91
4. 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 5. 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91