数据结构排序.ppt
第九章第九章 排序排序本章讨论数据结构中另一个重要的运算排序(或分类)，包括排序的定义定义、各种排序的方法、算法实现排序的方法、算法实现及时间复杂度时间复杂度的分析等内容。9.1 概述概述排序(Sort)是将无序的记录序列（或称文件）调整成有序的序列。 对文件（File）进行排序有重要的意义。如果文件按key有序，可对其折半查找，使查找效率提高；在数据库（Data Base）和知识库（Knowledge Base）等系统中，一般要建立若干索引文件，就牵涉到排序问题；在一些计算机的应用系统中，要按不同的数据段作出若干统计，也涉及到排序。排序效率的高低，直接影响到计算机的工作效率。另外，研究排序方法和算法，目的不单纯是完成排序的功能和提高效率，其中对软件人员的程序设计能力会有一定的提高，也是对以前数据结构内容的复习、巩固和提高。 1.排序定义排序定义 设含有n个记录的文件f=(R1 R2Rn)，相应记录关键字（key）集合k=k1 k2kn。若对1、2n的一种排列： P(1) P(2)P(n) （1P(i)n，ij时，P(i)P(j)）有： kP(1) kP(2) kP(n) 递增关系或 kP(1) kP(2) kP(n) 递减关系则使f 按key线性有序：（RP(1) RP(2)RP(n)），称这种运算为排序(或分类)。 关系符“”或“”并不一定是数学意义上的“小于等于”或“大于等于”，而是一种次序关系。但为讨论问题方便，取整型数作为key，故“”或“”可看作通常意义上的符号。2.稳定排序和非稳定排序稳定排序和非稳定排序 设文件f=（R1RiRjRn）中记录Ri、Rj（ij，i、j=1n）的key相等，即Ki=Kj。若在排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称这种排序是稳定的，其含义是它没有破坏原本已有序的次序。反之，若排序后Ri与Rj的次序有可能颠倒，则这种排序是非稳定的，即它有可能破坏了原本已有序记录的次序。 3.内排序和外排序内排序和外排序 若待排文件f在计算机的内存储器中，且排序过程也在内存中进行，称这种排序为内排序。内排序速度快，但由于内存容量一般很小，文件的长度（记录个数）n受到一定限制。若排序中的文件存入外存储器，排序过程借助于内外存数据交换（或归并）来完成，则称这种排序为外排序。我们重点讨论内排序的一些方法、算法以及时间复杂度的分析。 4.内排序方法内排序方法 截止目前，各种内排序方法可归纳为以下五类： （1）插入排序；（2）交换排序；（3）选择排序；（4）归并排序； （5）基数排序。 5.文件存储结构文件存储结构 （1）顺序结构）顺序结构类似线性表的顺序存储，将文件f=（R1 R2Rn）存于一片连续的存储空间，逻辑上相邻的记录在存储器中的物理位置也是相邻的，如图9.1： 在这种结构上对文件排序，一般要作记录的移动。当发生成片记录移动时，是一个很耗时的工作。 R1R2RiRn（2）链表结构）链表结构 类似于线性表的链式存储，文件中记录用节点来表示，其物理位置任意，节点之间用指针相连，如图9.2：链表结构的优点在于排序时无须移动记录，只需修改相应记录的指针即可。（3）地址映象结构）地址映象结构 该结构是另设一地址向量，存储文件中各记录的地址（或序号），如图9.3： R1 Rn L R1 Ri RjRn（数据文件数据文件） i j（地址向量地址向量） 排序可在地址向量上进行，一定程度上免去了排序时记录的移动。 9.2 插入排序插入排序 插入排序（Insert Sort）可分为：直接插入排序、折半插入排序、链表插入排序以及Shell（希尔）排序等。每种排序按照排序方法、举例说明、算法描述以及算法分析等几个步骤讨论。9.2.1 直接插入排序直接插入排序 设待排文件f=（R1 R2Rn）相应的key集合为k=k1 k2kn，文件f对应的结构可以是9.1节中讨论的三种文件结构之一。 1.排序方法排序方法 先将文件中的（R1）看成只含一个记录的有序子文件，然后从R2起，逐个将R2至Rn按key插入到当前有序子文件中，最后得到一个有序的文件。插入的过程上是一个key的比较过程，即每插入一个记录时，将其key与当前有序子表中的key进行比较，找到待插入记录的位置后，将其插入即可。另外，假定排序后的文件按递增次序排列（以下同）。例例9-1 设文件记录的key集合k=50，36，66，76，95，12，25，36（考虑到对记录次key排序的情况，允许多个key相同。如此例中有2个key为36，后一个表示成36，以示区别），按直接插入排序方法对k的排序过程如下： 直接插入排序直接插入排序k=50，36，66，76，95，12，25，3650 3636, 50 6636, 50, 66 7636, 50, 66, 76 9536, 50, 66, 76, 95 1212, 36, 50, 66, 76, 95 2512, 25, 36, 50, 66, 76, 95 3612, 25, 36, 36, 50, 66, 76, 95 一般, 插入ki（2in），当kjkikj+1ki-1时： k1 kj kj+1 ki-1 ki k1 kj ki kj+1 ki-1 直接插入排序直接插入排序文件结构说明：#define maxsize 1024 文件最大长度typedef int keytype; 设key为整型typedef struct 记录类型 keytype key; 记录关键字 记录其它域Retype;typedef struct 文件或表的类型 Retype Rmaxsize+1; 文件存储空间 int len; 当前记录数sqfile; 若说明sqfile F；则：（F.R1，F.R2F.RF.len）为待排文件，它是一种顺序结构；文件长度n=F.len；F.R0为工作单元，起到“监视哨”作用；记录的关键字ki写作F.Ri.key。 直接插入排序直接插入排序2.算法描述算法描述void Insort (sqfile F) 对顺序文件F直接插入排序的算法 int i,j; for (i=2;i=F.len;i+) 插入n1个记录 F.R0=F.Ri; 待插入记录先存于监视哨 j=i-1; while (F.R0.keyR3.key=25，low=3+1=4；28R5.key=35，high=51=4；28high，所以“28”应插在low=4所指示的位置 。lowhighhigh折半插入排序折半插入排序2.算法描述算法描述void Binsort (sqfile F) 对文件F折半插入排序的算法 int i,j,low,high,mid; for (i=2;i=F.len;i+) 插入n1个记录 F.R0=F.Ri; 待插入记录存入监视哨 low=1; high=i-1; while (low=F.Rmid.key) low=mid+1; 调整下界 else high=mid-1; 调整上界 for (j=i-1;j=low;j-) F.Rj+1=F.Rj; 记录顺移 F.Rlow=F.R0; 原Ri插入low位置 折半插入排序折半插入排序3.算法分析算法分析 插入Ri（2in）时，子表记录数为i1。同第八章中的折半查找算法的讨论，查找Ri的key比较次数为 ，故总的key比较次数C为：显然优于O(n2)。但折半插入排序的记录移动次数并未减少，仍为O(n2) 。故算法的时间复杂度T(n)仍为O(n2) 。9.2.3 链表插入排序链表插入排序设待排序文件f=（R1 R2Rn），对应的存储结构为单链表结构，如图9.4：1.排序方法排序方法 链表插入排序实际上是一个对链表遍历的过程。先将表置为空表，然后依次扫描链表中每个节点，设其指针为p，搜索到p节点在当前子表的适当位置，将其插入。 )log(log) 1(log2222nnOnniCni R1 Rn L )(log2iO链表插入排序链表插入排序例例9-3 设含4个记录的链表如图9.5 ： L 50 36 66 12 P插入插入50 ：初始化初始化 ： L 50 36 66 12 P插入插入36 ： L 36 50 66 12 P插入插入66 ： L 36 50 66 12 P插入插入12 ： L12 36 50 66 L50 36 66 12 2.算法描述算法描述typedef struct node 存放记录的节点 keytype key; 记录关键字 记录其它域 struct node *next; 链指针Lnode,*linklist;void Linsertsort (linklist L) 链表插入排序算法 linklist p,q,r,u; p=L-next; p为待插入节点指针 L-next=NULL; 置子表为空 while(p) 若待排序节点存在 r=L; q=L-next; r为q的前驱指针 while (q&q-keykey) 找p节点位置 r=q; q=q-next; u=p-next; p-next=q; r-next=p; 插入 p=u; L 36 50 46 12 prqrqu p3.算法分析算法分析（1）当链表L逆序时，每插入一个节点时，key的比较次数最多为1，总的key比较次数C达到最小，即：（2）当链表L正序时，每插入第i号（1in）节点都要搜索到当前子表的表尾，key的比较次数为i-1，故总的key比较次数C达到最大，即： 所以链表插入排序的时间复杂度T(n)=O(n2)。但排序过程中不牵涉到记录的移动，只是修改相应指针，这一点优于其它的插入排序方法。9.2.4 Shell排序排序 Shell（希尔）排序又称“缩小增量”排序，1959年由D.L.Shell提出。希尔发现：直接插入排序中，key比较次数及记录移动次数会比较大，若将待排序文件按某种次序分隔成若干个子文件，对各子文件“跳跃”式的排序，然后调整子文件个数，逐步对原文件排序，这样总的key比较次数尤其是记录移动次数也许会大大降低。 )(11minnOnCni)() 1() 1(2211maxnOnniCni1.Shell排序方法排序方法 设待排文件f=（R1 R2Rn），先将f中相隔增量d（如令d=n/2）的记录组成一个个子文件，对各子文件插入排序；然后缩小增量d（如令d=d/2），再将相隔新增量的记录组成一个个子文件，对诸子文件排序，直到增量d=1为止，排序完毕。这是一种跳跃式的排序方法，它使得文件逐步有序，从而克服了一次排序时记录成片移动现象。例例9-4 设文件的记录key集合k=50，36，66，76，95，12，25，36，24，08（n=10），选取增量序列为10/2=5、5/2=2、2/2=1。排序过程如下：序号： 1 2 3 4 5 6 7 8 9 10 50 36 66 76 95 12 25 36 24 0812502536366624760895令：令：d=5令：令：d=208123636762425506695令：令：d=1 08 12 24 25 36 36 50 66 76 95（完毕）（完毕）显然，Shell排序是非稳定排序。Shell排序排序2.算法描述算法描述void Shellsort (sqfile F) 对顺序文件F按Shell方法排序的算法 int i,j,d=F.len/2; 第一次增量 while (d=1) for (i=d+1;i0)&(F.R0.keyk2，则，则R1 R2；k2k3，若，若k2k3，则，则R2 R3； kn-1kn，若，若kn-1kn，则，则Rn-1 Rn。经过一趟比较之后，最大key的记录沉底，类似水泡。接着对前n1个记录重复上述过程，直到排序完毕。 n2log起泡排序起泡排序注意：在某趟排序的比较中，若发现两两比较无一记录交换，则说明文件已经有序，不必进行到最后两个记录的比较。例例9-5 设记录key集合k=50，36，66，76，95，12，25，36，排序过程如下： 排序完毕排序完毕
