概述插入排序 （直接插入、折半插入、表插入排序、希尔排序.ppt

《概述插入排序 （直接插入、折半插入、表插入排序、希尔排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、概述插入排序（直接插入、折半插入、表插入排序、希尔排序）交换排序（起泡排序、快速排序）选择排序（简单选择排序、树形选择排序、堆排序）归并排序基数排序小结第十章内部排序概述排序：将一组杂乱无章的数据排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。关键字(key):通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。每个数据表用哪个属性域作为关键字，要视具体的应用需要而定。即使是同一个表，在解决不同问题的场合也可能取不同的域做关键字。主关键字

2、:如果在数据表中各个对象的关键字互不相同，这种关键字即主关键字。按照主关键字进行排序，排序的结果是唯一的。次关键字:数据表中有些对象的关键字可能相同，这种关键字称为次关键字。按照次关键字进行排序，排序的结果可能不唯一。排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j]，它们的关键字k[i]==k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序；外排

3、序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象关键字序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。静态排序:排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放在一个顺序的表中。动态排序:给每个对象增加一

4、个链接指针，在排序的过程中不移动对象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺序，从而达到排序的目的。算法执行时所需的附加存储:评价算法好坏的另一标准。静态排序过程中所用到的数据表的定义，体现了抽象数据类型的思想。衡量排序方法的标准排序时所需要的平均比较次数排序时所需要的平均移动排序时所需要的平均辅助存储空间插入排序(InsertSorting)直接插入排序的基本思想是：当插入第i(i1)个对象时，前面的V[0],V[1],…,v[i-1]已经排好序。这时，用v[i]的关键字与v[i-1],v[i-2],…的关键字顺序进

5、行比较，找到插入位置即将v[i]插入，原来位置上之后的所有对象依次向后顺移。插入排序的基本方法是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。直接插入排序(InsertSort)各趟排序结果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=221254925*1608012345012345temp21254925*1608i=4012345temp21254925*1608

6、i=5i=325*16081649161621254925*1608012345012345temp21254925*08i=4时的排序过程012345temp21254925*完成160816i=4j=3i=4j=22525*161621254925*08012345012345temp214925*08012345temp21254925*160816162521i=4j=1i=4j=0i=4j=-116直接插入排序的算法（p265算法10.1）voidInsertSort(SqList&L){for(inti=2;i<=L.l

7、ength;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];//L.r[0]为监视哨for(intj=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}算法分析若设待排序的对象个数为L.length=n，则该算法的主程序执行n-1趟。关键字比较次数和对象移动次数与对象关键字的初始排列有关。最好情况下，排序前对象已经按关键字大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键字比较1次

8、，移动2次对象，总的关键字比较次数为n-1，对象移动次数为2(n-1)。分析：一个记录的辅助存储空间监视哨比较次数最小比较次数：Cmin=n-1最大比较次数：Cmax=平均比较次数：Cavg=(n-1)(n+4)/4移动次数最小移动次