数据结构之树和图算法

《数据结构之树和图算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、设n个记录的序列为{R1,R2,R3,...,Rn}其相应的关键字序列为{K1,K2,K3,...,Kn}若规定1,2,3,...,n的一个排列p1,p2,p3,...,pn，使得相应的关键字满足如下非递减关系:Kp≤Kp≤Kp≤...≤Kp123n则原序列变为一个按关键字有序的序列:Rp,Rp,Rp,...,Rp123n{}此操作过程称为排序。排序假设Ki=Kj，且排序前序列中Ri领先于Rj；若在排序后的序列中Ri仍领先于Rj，则称排序方法是稳定的。若在排序后的序列中Rj仍领先于Ri，则称排序方

2、法是不稳定的。例，序列3158869若排序后得3688915稳定的若排序后得3688915不稳定的稳定排序与不稳定排序内部排序:指的是待排序记录存放在计算机随机存储器中进行的排序过程。外部排序:指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。内部排序与外部排序排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的

3、比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。按照排序过程中所依据的原则的不同可以分类为:插入排序交换排序(快速排序)选择排序归并排序基数排序二叉排序树排序内部排序思想:利用有序表的插入操作进行排序有序表的插入:将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。例，序列132738657697插入4913273849657697插入排序——直接插入排序例，序列49386597761327初始，S

4、={49}；{3849}初始，令第1个元素作为初始有序表；依次插入第2,3,…,k个元素构造新的有序表；直至最后一个元素；{384965}{38496597}{3849657697}{133849657697}{13273849657697}直接插入排序算法主要应用比较和移动两种操作。直接插入排序算法描述voidinsertsort(ElemTypeR[],intn)//待排序元素用一个数组R表示，数组有n个元素{for(inti=1;i

5、mTypetemp=R[i];//把待排序元素赋给tempintj=i-1;while((j>=0)&&(temp

6、1=（n2-n）/2Mmax=3+4+…+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4Mmax=（n2+7n-8）/4因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。由于直接插入排序算法利用了有序表的插入操作，故顺序查找操作可以替换为折半查找操作。例，序列49386597761327设已形成有序表{3849659776}插入元素13折半插入排序算法:voidBinaryInsertSort(ElemTypeR[],intn){for(in

7、ti=1;i=left;j--)R[j+1]=R[j];//元素后移空出插入位R[left]=temp;}}折半插入效率分析二分插入

8、算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，因此二分插入排序的时间复杂度仍为O(n2)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。分析直接插入排序1.若待排序记录序列按关键字基本有序，则排序效率可大大提高；2.待排序记录总数越少，排序效率越高；希尔(shell)排序思想:先将待排序记录序列分割成为若干子序列分别进行直接插入排序；待整个序列中的记