数据结构与算法之内排序.ppt

《数据结构与算法之内排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、7内排序主要内容内部排序/外部排序稳定/不稳定排序排序算法性能分析内部排序算法2内排序设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{}此操作过程称为排序。排序3内排序内部排序:指的是待排序记录存放在计算机随机存储器中进行的排序过程。外部排序

2、:指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。内部排序与外部排序4内排序假设Ki=Kj，且排序前序列中Ri领先于Rj；若在排序后的序列中Ri仍领先于Rj，则称排序方法是稳定的。若在排序后的序列中Rj仍领先于Ri，则称排序方法是不稳定的。例，序列3158869若排序后得3688915稳定的若排序后得3688915不稳定的稳定排序与不稳定排序5内排序排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次

3、数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。6内排序按照排序过程中所依据的原则的不同可以分类为:插入排序交换排序选择排序归并排序基数排序二叉排序树排序内部排序7内排序思想:利用有序表的插入操作进行排序有序表的插入:将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。例，序列132738657697插入4913273849657697插入排序

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

5、n;i++)//i表示插入次数，共进行n-1次插入{ElemTypetemp=R[i];//把待排序元素赋给tempintj=i-1;while((j>=0)&&(temp

6、1Mmin=2（n-1）Cmax=1+2+…+n-1=（n2-n）/2Mmax=3+4+…+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4Mave=（n2+5n-6）/4因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。11内排序插入排序平均情况复杂度对每个i值，考虑平均情况下需要多少次比较。为简化分析，假设所有的值是不相同的，对一个i和临时变量x，x有i+1个位置可能会去012……….i-1x=A[i]比较次数和插入位置的关系：i=6A[0]A[1]A[2]

7、A[3]A[4]A[5]x=A[6]插入位置6543210比较次数123456612内排序插入排序平均情况复杂度在对序列没有其它任何信息的条件下,x到任何一个位置的概率都是1/(i+1).这样,对一个特定的值i,需要的平均比较次数为:把所有n-1次插入累加起来,有:13内排序由于直接插入排序算法利用了有序表的插入操作，故顺序查找操作可以替换为折半(二分法)查找操作。例，序列49386597761327设已形成有序表{3849657697}13插入元素13折半插入排序leftrightmidrightmid01234

8、5right{}97766549381314内排序算法:voidBinaryInsertSort(ElemTypeR[],intn){for(inti=1;i