1,第10章作业：10.1 10.6 10.8 10.25 10.42,实验报告：12周四截止，以班为单位交纸质文档,第3次上机时间：下周一晚（11月22号）,考试时间：14周二（12月7号）晚1921:00 考试方式：? 开/闭卷,2,10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序,第10章 内部排序,3,3,if ( low 1, /对顺序表L中的子序列r lowhigh 作快速排序,/一趟快排，将r 一分为二,/在左子区间进行递归快排，直到长度为1,/在右子区间进行递归快排，直到长度为1,pivot是局部变量,void QuickSort ( SqList ,对顺序表L进行快速排序的操作函数为：,int Partition(SqList &L,int low,int high) ,4,4,10.4 选择排序,选择排序有多种具体实现算法：1) 简单选择排序2) 锦标赛排序3) 堆排序,选择排序的基本思想是：每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i 个记录。,5,5,Winner (胜者),r1,锦标赛排序 建议每个记录多开两个特殊分量：,初态：,补足2k( k=log2n )个叶子结点,胜者树,第一趟：,6,课堂练习（2002级期末考试题）：,1. 给定一个由n个关键字不同的记录构成的序列，你能否用少于2n-3次比较找出n个元素中的最大值和最小值？如果有，请描述你的方法。最快需多少次比较？（无需写算法） (8分) 答：可以实现。选用锦标赛算法。两两元素比较，淘汰较小的，形如一棵二叉树。树根为最大值（此时用掉n-1次比较）。而最小者一定位于首次被淘汰之列。故只有 n/2个。一共需n-1+ n/2次比较。,1.5n-1 H.rim中除ri外，其他都具有堆特征。 现调整ri的值 ，使H.rim为堆。,20,基于初始堆进行堆排序的算法步骤：堆的第一个对象r0具有最大的关键码，将r0与rn对调，把具有最大关键码的对象交换到最后;再对前面的n-1个对象，使用堆的调整算法，重新建立堆。结果具有次最大关键码的对象又上浮到堆顶，即r0位置;再对调r0和rn-1，然后对前n-2个对象重新调整，如此反复，最后得到全部排序好的对象序列。,21,堆排序算法分析：,时间效率： O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法，而算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。,22,课堂练习（2002级期末考试题） ：,设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？ 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：（请自己计算） 堆排序的准确比较次数为： （请自己计算） 若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+n-10）=10n-55=10000-55=9945（次）,23,10.5 归并排序,归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。 更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 n / 2 个长度为 2 的有序子序列 ；再做两两归并，如此重复，直到最后得到一个长度为 n 的有序序列。,例：关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。,24,len=1,len=2,len=4,len=8,len=16,整个归并排序仅需log2n 趟，但每趟仍要比较和整理n个元素,25,一趟归并排序算法: (两路有序并为一路) 参见教材P283,void Merge (SR， / 将剩余的SRjn复制到TR / Merge,这就是能提高排序速度的原因,26,if ( s=t )TR1s=SRs; / 当1 = length时返回else /if / MSort,m=(s+t)/2; / 将SR st平分为SR sm和SR m+1tMSort (SR，/ 将TR2 sm和TR2 m+1t归并到TR1 st,void MSort (SR ,&TR1 ，s, t) / 将无序的SRst归并排序为TR1st,递归形式的两路归并完整排序算法: 参见教材P284,简言之，先由“长”无序变成“短”有序，再从“短”有序归并为“长”有序。,初次调用时为（L, L, 1, length）,27,归并排序算法分析：,时间效率： O(nlog2n),在每趟归并排序的操作中，要调用n/(2h)次Merge( )算法，将SR1n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在TR 1n中。另外，整个归并排序有log2n “层” ，所以算法总的时间复杂度为O(nlog2n)。空间效率： O(n) 因为需要一个与原始序列同样大小的辅助序列（TR）。这正是此算法的缺点。稳定性：稳定,28,10.6 基数排序 (Radix Sort),要讨论的问题： 1. 什么是“多关键字”排序？实现方法？ 2. 单逻辑关键字怎样“按位值”排序？,基数排序的基本思想是：,借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。,29,例1：对一副扑克牌该如何排序？若规定花色和面值的顺序关系为：花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A则可以先按花色排序，花色相同者再按面值排序；也可以先按面值排序，面值相同者再按花色排序。,最高位优先法MSD 先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。,最低位优先法LSD 先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）,30,因为有分组，故此算法需递归实现。,讨论：是借用MSD方式来排序好呢，还是借用LSD方式？,例：初始关键字序列T=（32, 13, 27, 32*, 19，33），请分别用MSD和LSD进行排序，并讨论其优缺点。,法1（MSD）：原始序列：32, 13, 27, 32*, 19， 33先按高位Ki1 排序：（13, 19）, 27, （32, 32*，33）再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33,