第7章 排序(Java版)ppt课件.ppt

《第7章 排序(Java版)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、排序。1、排序的定义2、排序的分类(1)、按排序过程中所涉及到的存储器不同分为：(2)、按相同关键字在排序前后的位置不同分为：稳定排序内部排序外部排序不稳定排序假设Ki=Kj（i≠j),且在排序前的序列中Ri领先于Rj（即i＜j)。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。3、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类

4、型：插入类交换类选择类归并类其它方法3、内部排序的方法(1).插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。(2).交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。(3).选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。(4).归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。(5).其它方法就

5、各类介绍一二个典型算法。下面就各类介绍一二个典型算法。4、排序算法的性能评价时间比较次数（与关键字值　比较）移动次数空间：指所需辅助空间的大小稳定性内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；待排序的顺序表记录类描述如下：publicclassRecordNode{privateComparablekey;//关键字privateObjectelement;//数据元素}5、待排序记录的类描述待排序的顺序表类publicclassSeqList{priva

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

7、i-1]R[i]无序序列R[i..n-1]一趟插入排序的基本思想：有序序列R[0..i]无序序列R[i+1..n-1]实现“一趟插入排序”可分三步进行：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

8、]中查找R[i]的插入位置”思想：先将第1个记录组成一个有序的子表，然后依次将后面的记录插入到这子表中，且一直保持它的有序性。7.2.1直接插入排序例：（43）21891543（2143）891543i=1（15214389)43i=3（1521434389）i=4(214389）1543i=2直接插入排序示例r0r1r2r3r4