数据结构第十章优秀PPT.ppt

《数据结构第十章优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构第十章优秀PPT.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 概述排序：将一个数据元素(或记录)的随意序列，重新排列成 一个按关键字有序的序列排序稳定性：若有两个关键字相同记录Ri和Rj,排序之前 Ri在Rj之前，排序后仍满足这种次序,这种排序是稳定的内部排序：对内存中数据进行排序内部排序分类：插入排序 交换排序 选择排序 归并排序 计数排序(1)插入排序v干脆插入排序v其它插入排序v希尔排序干脆插入排序：是一种最简洁的排序方法,它的基本操作思想是将一个记录插入到已排好序的有序表中,从而得到一个新的,记录数增1的有序表排序过程：将序列分成两部分，一部分已排序，一部分未排序，初始时，已经排序部分只有这个序列第一个元素依次取未排序中的每一个元素，插入到已排

2、序部分恰当位置.例：干脆插入排序干脆插入排序初始关键字 (49)38 65 97 76 13 27 49 i=2 (38)(38 49)65 97 76 13 27 49 i=3 (65)(38 49 65)97 76 13 27 49 i=4 (97)(38 49 65 97)76 13 27 49 i=5 (76)(38 49 65 76 97)13 27 49 i=6 (13)(13 38 49 65 76 97)27 49 i=7 (27)(13 27 38 49 65 76 97)49 i=8 (49)(13 27 38 49 49 65 76 97)干脆插入排序示例Void Ins

3、ertSort(SqList&L)/对依次表L作干脆插入排序 for (i=2;i=L.length;+i)if LT(L.ri.key,L.ri-1.key)L.r0=L.ri;/复制为哨兵 for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;/记录后移 L.rj+1=L.r0;/插入到正确位置 /InsertSort干脆插入排序算法算法分析干脆插入排序的空间困难度:O(1)时间困难度的分析:1.当待排序序列为正序时:须要进行n-1趟排序,每一趟只要进行一次比较,所以在排序过程中关键字的比较,移动记录的次数为 i=2 n 1,时间困难度为O(n)2.

4、当待排序序列为逆序时:须要进行n-1趟排序,在排序过程中,进行i=2 n(i)=(n+2)(n-1)/2次关键字的比较,记录移动的次数为i=2 n(i+1)=(n+4)(n-1)/2,所以时间困难度为O(n 2)一：折半插入排序 已排序部分本身有序，找插入位置时可以通过折半查找方法来确定插入位置，这样削减了元素比较次数，但没削减元素移动次数算法：Void BinsertSort(Sqlist&L)/对依次表L作折半插入排序 for(i=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;其它插入排序其它插入排序 while(low=high+1;-j)Lj+1=L

5、.rj;/记录后移 L.rhigh+1=L.r0;/插入 /for/BinsertSort二：2-路插入排序 在折半插入排序的基础上接着改进，目的是削减排序过程中移动记录的次数，但须要n个记录的协助空间,当l.r1.key是最小(或者最大)时,2-路插入排序就失去了优越性排序过程：原数组为data,开拓一个与data相等空间d将d构成一个循环数组，并设两个指针first和final分别 指向已排序部分第一个元素和最终一个元素将data0赋给d0，以d0将d分成两部分依次处理data1到datan-1 if(dataid0)用折半法将datai插入第一部分 else 用折半法插入其次部分例：Da

6、ta 49 38 65 97 76 13 27 49D D 13 27 38 49 49 65 76 97final49first38firstfinal49final6597first13first4938final762749三：表插入排序(目的是在排序过程中,不须要移动记录)#define SIZE 100 /静态链表容量Typedef struct RcdType rc;/记录项 int next;/指针项 SLNode;/表结点类型Typedef struct SLNode rSIZE;/0号单元为表头结点 int length;/链表当前长度SLinkListType;/静态链表类

7、型 设上述说明为静态链表类型作为待排记录序列的存储结构，为插入便利起见，设数组下标为“0”的重量为表头结点，并令表头结点记录的关键字取最大整数MAXINT则表插入排序过程描述如下：首先将静态链表中数组下标为“1”的重量(结点)和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量(结点)按记录关键字非递减插入到循环链表中 具体见p269图10。3 从表插入的基本操作仍是将一个记录插入到已经排好的有序表中。希尔排序思想：先将整个待排记录序列分希尔排序思想：先将整个待排记录序列分割成为若干子序列分别进行干脆插入排割成为若干子序列分别进行干脆插入排序，待整个序列中的记录序，待整个序列中的记

8、录“基本有序基本有序”时，再对全体记录进行一次干脆插入排时，再对全体记录进行一次干脆插入排序序希尔排序特点：子序列的构成不是简洁的希尔排序特点：子序列的构成不是简洁的“逐段分割是将相隔某个逐段分割是将相隔某个“增量增量”的记的记录组成一个子序列录组成一个子序列希尔排序 希尔排序示例初始关键字 49 38 65 97 76 13 27 49 55 04 d1=5 一趟排序结果13 27 49 55 04 49 38 65 97 76 d2=3二趟排序结果13 04 49 38 27 49 55 65 97 76 d3=1三趟排序结果：04 13 27 38 49 49 55 65 76 97Vo

9、id ShellInsert(Sqlist&L,int dk)/对依次表L作一趟希尔插入排序 for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;L.rj+dk=L.r0;ShellInsert 希尔排序算法 void ShellSort(SqList&L,int dlta,int t)/按递增序列dlta0.t-1对依次表L作希尔排序 for(k=0;kt;+t)ShellInsert(L,dltak);/一趟增量为dltak的插入排序ShellSort10。3起泡排序和快速排序起泡排序思想：依次对未排序部分相邻的两个元素进行比较,若

10、逆序则交换位置,每一趟可以使一个最大(最小)元素从这个序列中冒出来,经过n-1趟,就可以排好序例：起泡排序示例初始关键字 12 23 18 14 4 90第一趟排序后 12 23 18 14 4 90 其次趟排序后 12 18 14 4 23 第三趟排序后 12 14 4 18 第四趟排序后 12 4 14 第五趟排序后 4算法分析起泡排序结束条件为:一趟排序过程中,没有交换记录的操作.分析:1.当待排序序列为正序时:只要一趟排序,在排序过程中,进行n-1次关键字的比较,而且不移动记录,时间困难度为O(n)2.当待排序序列为逆序时:须要进行n-1趟排序,在排序过程中,进行i=2 n(i-1)=

11、n(n-1)/2次关键字的比较,并且作等数量的记录移动,所以时间困难度为O(n 2)快速排序快速排序思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录接着进行快速排序一趟快速排序的过程n1.在待排序序列中随意选择一个记录(通常选择第一个记录)作为枢轴记录L.rs.设枢轴记录的关键字为pivotkeyn2.设low指向待排序序列中的第一个记录,high指向待排序序列中的最终一个记录.n3.先将high向low方向扫描,若l.rhigh.key l.rlow.枢轴记录n4.再将 low向high 方向扫描,若l.rlow.keyp

12、ivotkey,则将 l.rlow=l.rhighn5.重复执行3,4两步,直到low=high时,再将pivotkey的记录=l.rlown到此,待排序序列以pivotkey为界,分成两部分:前一部分的记录关键字比后一部分小.再分别对这两部分进行快速排序例：对下列待排序序列进行快速排序 49l38132749初始关键字hh27 38 65 13 49hl第一次交换之后65l27 38 13 65 49 lh其次次交换之后27 38 13 65 49 第三次交换之后49lh完成一趟排序27 38 1365 49分别再进行快速排序分别再进行快速排序最终得到有序序列13 27 38 49 49 6

13、5算法10.6(a)Int Partition(SqList&L,int low,int high)pivotkey=L.rlow.key;While(lowhigh)while(low=pivotkey)-high;L.rlowL.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rlowL.rhigh;return low;/返回枢轴记录的位置/Partition快速排序算法实现改写上述算法：将枢轴暂存在r0的位置上，直至一趟排序结束后再将枢轴记录移至正确位置上，算法10.6(b)：Int Partition(SqList&L,int low,i

14、nt high)L.r0=L.rlow;Pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlow=L.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;/枢轴记录到位 return low;/Partition算法10.7 void Qsort(SqList&L,int low,int high)if (lowhigh)pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);

15、Qsort(L,pivotloc+1,high);/Qsort算法10.8Void QuickSort(Sqlist&L)Qsort(L,1,L.length);/QuickSort;递归形式的快速排序算法快速排序算法分析 假设n个关键字是等概率分布的,第k个位置是通过调用Partition后的枢轴记录应当处的位置,它将文件分成两部分:前一部分有k-1个记录,后一部分有n-k个记录.设T(n)是快速排序的平均时间,则依据算法QuickSort可以得到下列递归公式,设k为1,2n中的随意一个值并且概率相同.快速排序算法分析 T(n)=Cn+1/nk=2 n(T(k-1)+T(n-k)T(1)=T

16、(0)=0求解此递归方程:得到:T(n)=2(n+1)log2 n+O(n)时间困难度:O(nlog2n)空间困难度:O(log2n)稳定性质:不稳定 10。4选择排序简洁选择排序树形选择排序堆排序算法思想:每一趟在n-i+1个记录中(i=1,2,3.n-1)选出关键字最小的记录作为有序列中的第i个记录.一趟简洁选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小记录，并和第i(1=i=n)个记录交换之,使得待排序部分增加一个记录简洁选择排序简洁选择排序简洁选择排序算法10.9：void SelectSort(Sqlist&L)for(i=1;iL.length;+

17、i)j=SelectMinKey(L,i);if(i!=j)L.riL.rj;/SelectSort 为了削减“比较”关键字的次数，引出树形选择排序树形选择排序：又称锦标赛排序，是一种依据锦标赛思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，得到n/2个较小者,然后再对对 n/2个较小者进行两两比较，如次重复，直至选出最小关键字的记录为止.这个过程可用一棵有n个叶子结点的完全二叉树表示树形选择排序树形选择排序树形选择排序示例初始关键字 49 38 65 97 76 13 27 492749271313763865976538384913最小者输出：132713输出13762727输

18、出27384949657697同理得出38 树形选择排序削减了比较次数，但是辅存增加了，于是为了弥补这个缺点，引出堆排序堆：是一棵完全二叉树，全部根结点小于等于或大于等 于其孩子结点值堆排序：若在输出堆顶的最小值之后，使得剩余n-1个元 素得序列重又建成一个堆，则输出n个元素的次 小值。如此反复执行，便得到一个有序序列,这 个过程称为堆排序堆排序堆排序堆排序的过程堆排序:如何将无序序列构成一个堆 输出堆顶元素 将剩余元素重新构成一个堆 重复执行(2)和(3)直到所以元素全部输出，输出序列就是排好序的有序序列如何将一个无序序列构成为一个堆?n方法:n1.将无序序列按依次构成一棵完全二叉树.n2.

19、从完全二叉树的最终一个非终端结点起先反复进行自上而下的”筛选”.最终一个非终端结点的编号为n/2下取整.n”筛选”:将该结点值与其孩子结点值进行比较,若不符合堆的定义,则与其孩子中的小者交换,这个”筛选”过程直到叶结点或者满足堆的定义如何将剩余元素构成一个堆?n输出堆顶元素后,用堆尾元素代替堆顶元素,然后再从根结点向叶结点方向”筛选”,构成一个新的堆.要进行堆排序首先要把一个无序序列建成一个堆，这个过程也叫“筛选”过程，如图说明：无序序列769738134927654997被筛选之后的状态4997651365被筛选之后的状态38被筛选之后的状态49被筛选之后建成的堆134927算法10.10：

20、typedef SqList HeapType;/堆接受依次表存储表示Void HeadAdjust(HeapType&H,int s,int m)/已知H.rs.m中,记录的关键字除H.rs.key之外均满足堆的定义，本函数调整H.rs的关键字，使H.rs.m成为一个大顶堆(对其中记录的关键字而言)Rc=H.rs;For(j=2*s;j=m;j*=2)/沿key较大的孩子结点向下筛选堆排序算法实现 if(j0;-i)/把H.r1.H.length建成大顶堆 HeapAdjust(H.i,H.length);for(i=H.length;i1;-i)H.r1H.ri;/将堆顶记录和当前未经排序

21、 子序列Hr1.i中 最终一个记录相互交换 HeapAdjust(H,1,i-1);/将H.r1.i-1重新调整为大顶堆/HeapSort例：堆排序在堆顶输出一个小元素后，以堆中最终一个元素替代之，再重新排成一个小堆顶堆496527977638491349652713763849输出堆顶13,以最终一个元素97替代之9797654976384927调整建成新堆同理接着重复上述操作，接着输出堆顶27，把最终一个元素替代之，接着输出全部元素堆排序算法分析n堆排序的运行时间主要耗费在建立初始堆和将剩余元素构成新堆而进行的反复筛选上.T(n)=T(建堆)+T(重新构堆)n对深度为k的堆,筛选算法中进行

22、的关键字的比较次数至多为2(k-1)n(1)建立堆:建立含有n个记录,深度为h的堆时,总共进行关键字的比较次数不超过4n,具体请见P282的下批.n(2)重新构造堆:因为n个结点的完全二叉树深度为log2n上取整+1,而调整建立新堆调用HeapAdjust过程n-1次,所以总共进行的比较次数不超过2n(log2n)堆排序算法分析时间困难度:O(nlog2n)空间困难度:O(1)稳定性质:不稳定 10.5归并排序归并排序思想：是又一类不同的 排序方法。“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。归并排序过程：假设初始序列含有n个记录，则可看成是n个有序的子序列；再两两归并，如此

23、重复，直至得到一个长度为n的有序序列为止，这种方法称为2-路 归并 排序归并排序特点：比较稳定 2-路归并排序核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列2-路归并排序示例初始关键字 49 38 65 97 76 13 27一趟归并之后 38 49 65 97 13 76 27二趟归并之后 38 49 65 97 13 27 76三趟归并之后 13 27 38 49 65 76 97算法10.12：Void Merge(RcdType SR,RcdType&TR,int m,int n)/将有序的SRi.m和SRm+1.n归并为有序的TRi.nFor (j=m+1,k=i;i

24、=m&j=n;+k)/将SR中记录由小到大地并入TR if LQ(SRi.key,SRj.key)TRk=SRi+1;else TRk=SRj+;2-路归并排序算法 if (i=m)TRk.n=SRi.m;/将剩余的SRi.m复制到TR if(j=n)TRk.n=SRj.n;/将剩余的SRj.n复制到TR/Mergen算法10.13nVoid msort(Rcdtype SR,Rcdtype&TR,int s,int t)/将SRs.t归并排序为TRs.t;if(s=t)TR1s=SRs;else m=(s+t)/2;/将SRs.t平分为SRs.m SRm+1.t MSort(SR,TR2,s

25、,m);/递归地将SRs.m归并为 TR2s.m MSort(SR,TR2,m+1,t);/递归地将SRm+1.t归并为 TR2m+1.t Merge(TR2,TR1,s,m,t);/将TR2s.m 和TR2m+1.t归并为 TR1s.t n算法10.14n void MergeSort(Sqlist&L)n /对依次表L进行归并排序n Msort(L.r,L.r,1,L.length);n 归并排序算法分析n(1)整个排序须要log2n上取整趟n(2)而一趟排序,调用n/2h次算法merge将SR1.n中前后相邻且长度为h的有序段进行两两归并,并且存储在TR1.n中n时间困难度:O(nlog

26、2n)n空间困难度:O(n)n 稳定性质:稳定 基数排序基数排序思想：是 一种借助多关键字排序的思想对单逻辑关键字进行排序的方法v多关键字排序v链式基数排序最高位优先排序（MSD）：先对主关键字进行排序，将序列份成若干个子序列，然后分别就每个子序列对关键字进行排序，依次重复，直到进行排序之后每个子序列的记录都具有相同的关键字，再分别对每个子序列进行排序，最终将全部子序列依次联接在一起成为有序序列。最低位优先法（LSD)：从最次位关键字进行排序，然后再对高一位的关键子进行排序，依次重复，直至对最高位主关键字进行排序后便成为一个有序序列。多关键字排序多关键字排序链式基数排序链式基数排序 基数排序是

27、借助“安排”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法链式基数排序示例278 109 063 930e0 e1 e2 e3 e4 e5 e6 e7 e8 e9930 063 278 109f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 930 063 278 109e0 e1 e2 e3 e4 e5 e6 e7 e8 e9109 930 063 278F0 f3 .f6 f7 109 930 063 278E0 e1 e2 e3 e4 e5 e6 e7 e8 e9063 109 278 930F0 f1 f2 .f9063 109 278 930算法10.17：Vo

28、id RadixSort(SLList&L)for(i=0;iL.recnum;+i)L.ri=i+1;L.rL.recnum.next=0;/将L改造成静态链表 for(i=0;iL.keynum;+i)Distribute(L.r,i,f,e);/第i趟安排 Collect(L.r,i,f,e);/第i趟收集 /RadixSort链式基数排序算法链式基数排序算法各种内部排序方法的比较探讨综合比较各章内探讨的各种内部排序方法，大致有如下结果：排序方法平均时间最坏情况辅助存储简单排序快速排序堆排序归并排序基数排序O(n2)O(nlogn)O(nlogn)O(nlogn)O(d(n+rd)O(n

29、2)O(n2)O(nlogn)O(nlogn)O(d(n+rd)O(1)O(logn)O(1)O(n)O(rd)从上表中得出以下结论：从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏状况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时，归并排序所需时间较堆排序省，但它所需的协助存储量最多。上表中的“简洁排序”包括除希尔排序之外的全部插入排序，起泡排序和简洁排序，其中以干脆插入排序为最简洁，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法，因此常将它和其它的排序方法，诸如快速排序，归并排序等结合在一起运用基数排序的时间困难度也可写成O(d*n)。依次它适合n值很大而关键字较小的序列。从方法的稳定性来比较，基缩排序是稳定的内排方法，全部时间困难度为O(n2)的简洁排序法也是稳定的，然而，快速排序，堆排序和希尔排序等时间性能较好的排序方法都是不稳定的