数据结构JAVA语言描述习题答案(刘小晶等主编).第7章-排序(Java版)

数据结构(Java语言描述)1第七章排序数据结构（Java语言描述）第七章排序章节目录作业布置结束放映教学内容7.1排序的基本概念7.2插入排序7.3交换排序7.4选择排序7.5归并排序7.6基数排序数据结构（Java语言描述）第七章排序章节目录作业布置结束放映教学重点与难点重点：掌握排序的基本概念以及各种常见排序方法的实现。难点：希尔排序、快速排序、归并排序和堆排序等高效排序方法。数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录4【课前思考】1.熟悉排序吗？过去曾经学过哪些排序方法？在第一章中曾以选择排序和起泡排序为例讨论算法实际复杂度．2.自己有没有编过排序的程序？是用的什么策略？数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录51、排序的定义3、内部排序的方法4、排序算法的性能评价5、待排序记录的类描述2、排序的分类7.1排序的基本概念数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录61、排序的定义排序是计算机内经常进行的一种操作，是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录7严格定义如下：一般情况下，假设含n个记录的序列为{R0,R1,…，Rn-1}其相应的关键字序列为{K0,K1,…，Kn-1}这些关键字相互之间可以进行比较，且在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。1、排序的定义数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录8关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录92、排序的分类(1)按排序过程中所涉及到的存储器不同分为：(2)按相同关键字在排序前后的位置不同分为：稳定排序内部排序外部排序不稳定排序假设Ki=Kj（i≠j),且在排序前的序列中Ri领先于Rj（即i＜j)。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录103、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录11基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法3、内部排序的方法数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录12(1)插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录13(2)交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录14(3)选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录15(4)归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。(5)其它方法就各类介绍一二个典型算法。如：基数排序下面就各类介绍一二个典型算法。数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录164、排序算法的性能评价时间比较次数（与关键字值比较）移动次数空间：指所需辅助空间的大小稳定性数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录17内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录18待排序的顺序表记录类描述如下:(P242)publicclassRecordNode{privateComparablekey;//关键字privateObjectelement;//数据元素……}备注：1.key为Comparable接口类型，它能够赋值为任何实现Comparable接口类的对象。2.element为Object类型，在实际应用时，可根据不同问题定义为不同的具体类。5、待排序记录的类描述数据结构（Java语言描述）7.1排序的基本概念作业布置结束放映章节目录19待排序的顺序表类(P243)publicclassSeqList{privateRecordNode[]r;//顺序表记录结点数组privateintcurlen;//顺序表长度，即记录个数//构造方法:构造一个存储空间容量为maxSize的顺序表publicSeqList(intmaxSize){this.r=newRecordNode[maxSize];//为顺序表分配maxSize个存储单元this.curlen=0;//置顺序表的当前长度为0}……}数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序20总思想：每次将一个待排序的记录，按其关键字值的大小插入到前面已排序好的记录序列中的适当位置，直到全部记录插入完成为止。7.2插入排序数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序21有序序列r[0..i-1]R[i]无序序列r[i..n-1]一趟插入排序的基本思想：有序序列r[0..i]无序序列r[i+1..n-1]数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序22实现“一趟插入排序”可分三步进行：3．将r[i]插入(复制)到r[j+1]的位置上。2．将r[j+1..i-1]中的所有记录均后移一个位置；1．在r[0..i-1]中查找r[i]的插入位置，r[0..j].keyr[i].keyr[j+1..i-1].key；数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序23直接插入排序（基于顺序查找）确定插入位置的查找方法不同导致不同的算法描述：希尔排序（基于逐趟缩小增量）7.2插入排序数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序24待排序记录依次存放在数组r[0..n-1]中。思想：先将第0个记录组成一个有序的子表，然后依次将后面的记录插入到这子表中，且一直保持它的有序性。7.2.1直接插入排序-不带监视哨的算法基本条件：数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序25例：（43）21891543（1521434389）i=4i=1（2143）891543(214389）1543i=2直接插入排序示例r0r1r2r3r443218915437.2.1直接插入排序-不带监视哨的算法（15214389)43i=3数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序26实现直接插入排序的步骤为：(P244)2）后移并插入3）令i=1，2，…,n-1,重复1）、2），实现整个序列的排序。1）查找r[i]的插入位置7.2.1直接插入排序-不带监视哨的算法将r[i]暂存在临时变量temp中，将temp与r[j](j=i-1,…，0）依次进行比较如何查找？数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序27publicvoidinsertSort(){RecordNodetemp;inti,j;for(i=1;ithis.curlen;i++){//n-1趟扫描temp=r[i];//第i条记录暂存在temp中for(j=i-1;j=0&&temp.getKey().compareTo(r[j].getKey())0;j--){r[j+1]=r[j];//后移}r[j+1]=temp;//r[i]插入到第j+1个位置}}7.2.1直接插入排序-不带监视哨的算法P245算法7.1算法需进行改进！！数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序28此算法中第6行的循环条件中的“j=0”用来控制下标越界。为了提高算法效率，可对该算法进行如下改进：首先将待排序的n条记录从下标为1的存储单元开始依次存放在数组r中，再将顺序表的第0个存储单元设置为一个“监视哨”，即在查找之前把r[i]赋给r[0]，这样每循环一次只需要进行记录的比较，不需要比较下标是否越界7.2.1直接插入排序-带监视哨的算法数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序29例：初始关键字：（43）21891543(21)（2143）891543i=2(15)（15214389)43i=4(43)（1521434389）i=5(89)(214389）1543i=3直接插入排序示例r0r1r2r3r4r54321891543数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序30从r[i-1]起向前进行顺序查找，监视哨设置在r[0]；r[0]=r[i];//设置“哨兵”循环结束表明r[i]的插入位置为j+1r[0]jr[i]for(j=i-1;r[0].getKeyr[j].getKey;--j);//从后往前找j=i-1插入位置如何查找到r[i]的插入位置？7.2.1直接插入排序-带监视哨的算法数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序31对于在查找过程中找到的那些关键字不小于R[i].key的记录，在查找的同时实现记录向后移动；for(j=i-1;r[0].getKeyr[j].getKey;--j)r[j+1]=r[j]；r[0]jr[i]j=i-1上述循环结束后可以直接进行“插入”插入位置后移并插入7.2.1直接插入排序-带监视哨的算法数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序32令i=2，…,curlen-1,实现整个序列的排序。for(i=2;i=curlen;++i){在r[0..i-1]中查找r[i]的插入位置;插入r[i];}7.2.1直接插入排序-带监视哨的算法数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序33voidinsertSortWithGuard()(){//对顺序表作直接插入排序。for(i=2;i=this.curlen;++i){}}r[0]=r[i];//复制为监视哨for(j=i-1;r[0].getKey().compareTo(r[j].getKey())0;j--)r[j+1]=r[j];//记录后移r[j+1]=r[0];//插入到正确位置7.2.1直接插入排序-带监视哨的算法P245算法7.2数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序34不带监视哨的直接插入排序性能分析：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：1111nni02)1)(4()2(11nnini“移动”的次数：“移动”的次数：2)2)(1(11nnini数据结构（Java语言描述）作业布置结束放映章节目录7.2插入排序35平均值：约n2/4１.直接插入排序的时间复杂度：2.只需记录的辅助空间３.是的排序方法一个稳