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

《数据结构JAVA语言描述习题答案(刘小晶等主编).第7章-排序(Java版).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第七章排序1教学内容7.1排序的基本概念7.2插入排序7.3交换排序7.4选择排序7.5归并排序7.6基数排序教学重点与难点重点：掌握排序的基本概念以及各种常见排序方法的实现。难点：希尔排序、快速排序、归并排序和堆排序等高效排序方法。【课前思考】1.熟悉排序吗？过去曾经学过哪些排序方法？在第一章中曾以选择排序和起泡排序为例讨论算法实际复杂度．2.自己有没有编过排序的程序？是用的什么策略？41、排序的定义3、内部排序的方法4、排序算法的性能评价5、待排序记录的类描述2、排序的分类7.1排序的基本概念51、排序的定义排序是计

2、算机内经常进行的一种操作，是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,976严格定义如下：一般情况下，假设含n个记录的序列为{R0,R1,…，Rn-1}其相应的关键字序列为{K0,K1,…，Kn-1}这些关键字相互之间可以进行比较，且在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排

3、序。1、排序的定义7关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。82、排序的分类(1)按排序过程中所涉及到的存储器不同分为：(2)按相同关键字在排序前后的位置不同分为：稳定排序内部排序外部排序不稳定排序假设Ki=Kj（i≠j),且在排序前的序列中Ri领先于Rj（即i＜j)。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。93、内

4、部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区10基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法3、内部排序的方法11(1)插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。12(2)交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。13(3)选择类从记录的无序子序列中“选

5、择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。14(4)归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。(5)其它方法就各类介绍一二个典型算法。如：基数排序下面就各类介绍一二个典型算法。154、排序算法的性能评价时间比较次数（与关键字值比较）移动次数空间：指所需辅助空间的大小稳定性16内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；17待排序的顺序表记录类描述如下:(P242)public

6、classRecordNode{privateComparablekey;//关键字privateObjectelement;//数据元素……}备注：1.key为Comparable接口类型，它能够赋值为任何实现Comparable接口类的对象。2.element为Object类型，在实际应用时，可根据不同问题定义为不同的具体类。5、待排序记录的类描述18待排序的顺序表类(P243)publicclassSeqList{privateRecordNode[]r;//顺序表记录结点数组privateintcurlen;//

7、顺序表长度，即记录个数//构造方法:构造一个存储空间容量为maxSize的顺序表publicSeqList(intmaxSize){this.r=newRecordNode[maxSize];//为顺序表分配maxSize个存储单元this.curlen=0;//置顺序表的当前长度为0}……}19总思想：每次将一个待排序的记录，按其关键字值的大小插入到前面已排序好的记录序列中的适当位置，直到全部记录插入完成为止。7.2插入排序20有序序列r[0..i-1]R[i]无序序列r[i..n-1]一趟插入排序的基本思想：有序序列

8、r[0..i]无序序列r[i+1..n-1]21实现“一趟插入排序”可分三步进行：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].key