数据结构第十章.ppt

概述,排序：将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列排序稳定性：若有两个关键字相同记录Ri和Rj,排序之前Ri在Rj之前，排序后仍满足这种次序,这种排序是稳定的内部排序：对内存中数据进行排序内部排序分类：插入排序交换排序选择排序归并排序计数排序,(1)插入排序,直接插入排序其它插入排序希尔排序,直接插入排序：是一种最简单的排序方法,它的基本操作思想是将一个记录插入到已排好序的有序表中,从而得到一个新的,记录数增1的有序表排序过程：将序列分成两部分，一部分已排序，一部分未排序，初始时，已经排序部分只有这个序列第一个元素依次取未排序中的每一个元素，插入到已排序部分恰当位置.例：,直接插入排序,初始关键字(49)38659776132749i=2(38)(3849)659776132749i=3(65)(384965)9776132749i=4(97)(38496597)76132749i=5(76)(3849657697)132749i=6(13)(133849657697)2749i=7(27)(13273849657697)49i=8(49)(1327384949657697),直接插入排序示例,VoidInsertSort(SqList/插入到正确位置/InsertSort,直接插入排序算法,算法分析,直接插入排序的空间复杂度:O(1)时间复杂度的分析:1.当待排序序列为正序时:需要进行n-1趟排序,每一趟只要进行一次比较,所以在排序过程中关键字的比较,移动记录的次数为i=2n1,时间复杂度为O(n)2.当待排序序列为逆序时:需要进行n-1趟排序,在排序过程中,进行i=2n(i)=(n+2)(n-1)/2次关键字的比较,记录移动的次数为i=2n(i+1)=(n+4)(n-1)/2,所以时间复杂度为O(n2),一：折半插入排序已排序部分本身有序，找插入位置时可以通过折半查找方法来确定插入位置，这样减少了元素比较次数，但没减少元素移动次数算法：VoidBinsertSort(Sqlist,其它插入排序,while(low=high+1;-j)Lj+1=L.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-1if(dataipivotkey,则将l.rlow=l.rhigh5.重复执行3,4两步,直到low=high时,再将pivotkey的记录=l.rlow到此,待排序序列以pivotkey为界,分成两部分:前一部分的记录关键字比后一部分小.再分别对这两部分进行快速排序,例：对下列待排序序列进行快速排序,49,l,38,13,27,初始关键字,h,h,2738651349,h,l,第一次交换之后,65,l,2738136549,l,h,第二次交换之后,2738136549,第三次交换之后,49,l,h,完成一趟排序,273813,6549,分别再进行快速排序,分别再进行快速排序,最后得到有序序列,132738494965,算法10.6(a)IntPartition(SqList/返回枢轴记录的位置/Partition,快速排序算法实现,改写上述算法：将枢轴暂存在r0的位置上，直至一趟排序结束后再将枢轴记录移至正确位置上，算法10.6(b)：IntPartition(SqList,L.rlow=L.rhigh;while(lowhigh/Partition,算法10.7voidQsort(SqList,递归形式的快速排序算法,快速排序算法分析,假设n个关键字是等概率分布的,第k个位置是通过调用Partition后的枢轴记录应该处的位置,它将文件分成两部分:前一部分有k-1个记录,后一部分有n-k个记录.设T(n)是快速排序的平均时间,则根据算法QuickSort可以得到下列递归公式,设k为1,2n中的任意一个值并且概率相同.,快速排序算法分析,T(n)=Cn+1/nk=2n(T(k-1)+T(n-k)T(1)=T(0)=0求解此递归方程:得到:T(n)=2(n+1)log2n+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：voidSelectSort(Sqlist/SelectSort,为了减少“比较”关键字的次数，引出树形选择排序树形选择排序：又称锦标赛排序，是一种按照锦标赛思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，得到n/2个较小者,然后再对对n/2个较小者进行两两比较，如次重复，直至选出最小关键字的记录为止.这个过程可用一棵有n个叶子结点的完全二叉树表示,树形选择排序,树形选择排序示例,初始关键字4938659776132749,27,49,27,13,13,76,38,65,97,65,38,38,49,13,最小者输出：,13,27,76,27,38,树形选择排序减少了比较次数，但是辅存增加了，于是为了弥补这个缺点，引出堆排序堆：是一棵完全二叉树，所有根结点小于等于或大于等于其孩子结点值堆排序：若在输出堆顶的最小值之后，使得剩余n-1个元素得序列重又建成一个堆，则输出n个元素的次小值。如此反复执行，便得到一个有序序列,这个过程称为堆排序,堆排序,堆排序的过程,堆排序:如何将无序序列构成一个堆输出堆顶元素将剩余元素重新构成一个堆重复执行(2)和(3)直到所以元素全部输出，输出序列就是排好序的有序序列,如何将一个无序序列构成为一个堆?,方法:1.将无序序列按顺序构成一棵完全二叉树.2.从完全二叉树的最后一个非终端结点开始反复进行自上而下的”筛选”.最后一个非终端结点的编号为n/2下取整.”筛选”:将该结点值与其孩子结点值进行比较,若不符合堆的定义,则与其孩子中的小者交换,这个”筛选”过程直到叶结点或者满足堆的定义,如何将剩余元素构成一个堆?,输出堆顶元素后,用堆尾元素代替堆顶元素,然后再从根结点向叶结点方向”筛选”,构成一个新的堆.,要进行堆排序首先要把一个无序序列建成一个堆，这个过程也叫“筛选”过程，如图说明：,无序序列,76,97,38,97被筛选之后的状态,65被筛选之后的状态,38被筛选之后的状态,49被筛选之后建成的堆,算法10.10：typedefSqListHeapType;/堆采用顺序表存储表示VoidHeadAdjust(HeapTypej*=2)/沿key较大的孩子结点向下筛选,堆排序算法实现,if(jm/插入/HeadAdjust,堆排序算法10.11：voidHeapSort(HeapType/将H.r1.i-1重新调整为大顶堆/HeapSort,例：,堆排序在堆顶输出一个小元素后，以堆中最后一个元素替代之，再重新排成一个小堆顶,堆,49,65,27,13,76,38,输出堆顶13,以最后一个元素97替代之,97,97,65,49,76,38,27,调整建成新堆,同理继续重复上述操作，接着输出堆顶27，把最后一个元素替代之，继续输出全部元素,堆排序算法分析,堆排序的运行时间主要耗费在建立初始堆和将剩余元素构成新堆而进行的反复筛选上.T(n)=T(建堆)+T(重新构堆)对深度为k的堆,筛选算法中进行的关键字的比较次数至多为2(k-1)(1)建立堆:建立含有n个记录,深度为h的堆时,总共进行关键字的比较次数不超过4n,具体请见P282的下批.(2)重新构造堆:因为n个结点的完全二叉树深度为log2n上取整+1,而调整建立新堆调用HeapAdjust过程n-1次,所以总共进行的比较次数不超过2n(log2n),堆排序算法分析,时间复杂度:O(nlog2n)空间复杂度:O(1)稳定性质:不稳定,10.5归并排序,归并排序思想：是又一类不同的排序方法。“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。归并排序过程：假设初始序列含有n个记录，则可看成是n个有序的子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种方法称为2-路归并排序归并排序特点：比较稳定2-路归并排序核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列,2-路归并排序示例,初始关键字49386597761327,一趟归并之后38496597137627,二趟归并之后38496597132776,三趟归并之后13273849657697,算法10.12：VoidMerge(RcdTypeSR,RcdType,2-路归并排序算法,if(i=m)TRk.n=SRi.m;/将剩余的SRi.m复制到TRif(j=n)TRk.n=SRj.n;/将剩余的SRj.n复制到TR/Merge,算法10.13Voidmsort(RcdtypeSR,Rcdtype/将SRs.t平分为SRs.mSRm+1.t,MSort(SR,TR2,s,m);/递归地将SRs.m归并为TR2s.mMSort(SR,TR2,m+1,t);/递归地将SRm+1.t归并为TR2m+1.tMerge(TR2,TR1,s,m,t);/将TR2s.m和TR2m+1.t归并为TR1s.t,算法10.14voidMergeSort(Sqlist,归并排序算法分析,(1)整个排序需要log2n上取整趟(2)而一趟排序,调用n/2h次算法merge将SR1.n中前后相邻且长度为h的有序段进行两两归并,并且存储在TR1.n中时间复杂度:O(nlog2n)空间复杂度:O(n)稳定性质:稳定,基数排序,基数排序思想：是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法多关键字排序链式基数排序,最高位优先排序（MSD）：先对主关键字进行排序，将序列份成若干个子序列，然后分别就每个子序列对关键字进行排序，依次重复，直到进行排序之后每个子序列的记录都具有相同的关键字，再分别对每个子序列进行排序，最后将所有子序列依次联接在一起成为有序序列。最低位优先法（LSD)：从最次位关键字进行排序，然后再对高一位的关键子进行排序，依次重复，直至对最高位主关键字进行排序后便成为一个有序序列。,多关键字排序,链式基数排序,基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法,链式基数排序示例,278109063930,e0e1e2e3e4e5e6e7e8e9,930063278109,f0f1f2f3f4f5f6f7f8f9,930063278109,E0e1e2e3e4e5e6e7e8e9,063109278930,F0f1f2.f9,算法10.17：VoidRadixSort(SLList/第i趟收集/RadixSort,链式基数排序算法,各种内部排序方法的比较讨论,综合比较各章内讨论的各种内部排序方法，大致有如下结果：,从上表中得出以下结论：从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时，归并排序所需时间