数据结构与算法-第21讲插入排序

1第21讲插入排序本讲知识点：(1)了解排序的相关基础知识(2)掌握插入排序、希尔排序的算法难点：希尔排序2排序的基本概念各种排序方法各种排序方法的比较排序知识体系结构排序

插入排序

选择排序交换排序

归并排序基数排序直接插入排序折半插入排序链表插入排序希尔排序直接选择排序堆排序冒泡排序快速排序3一、排序的定义Sorting排序的基本概念假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：

Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为

{Rp1,Rp2,…，Rpn}的操作称作排序。4排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序的基本概念一、排序的定义Sorting学号姓名高数英语思想品德0001王军85880002李明64920003汤晓影8586………687278……5学号姓名高数英语思想品德0001王军85880002李明64920003汤晓影8586………687278……排序的基本概念单键排序：根据一个关键码进行的排序；多键排序：根据多个关键码进行的排序。按学号排序——单键排序按成绩（高数＋英语＋思想品德）排序——多键排序一、排序的定义Sorting61.

内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中2.外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。排序的分类外部排序：多路平衡归并、置换-选择。一、排序的定义Sorting71.基于比较：基本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为Ω（nlog2n）。2.不基于比较：根据关键码的分布特征。基于比较的内排序1.插入排序2.交换排序3.选择排序4.归并排序5.基数排序排序的分类一、排序的定义Sorting8排序算法的性能1.基本操作。内排序在排序过程中的基本操作：⑴比较：关键码之间的比较；⑵移动：记录从一个位置移动到另一个位置。2.辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。3.算法本身的复杂程度。

一、排序的定义Sorting91、直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。二、插入排序InsertionSort10有序序列elem[0..i-1]elem[i]无序序列elem[i..n-1]一趟直接插入排序的基本思想：有序序列elem[0..i]无序序列elem[i+1..n-1]11实现“一趟插入排序”可分三步进行：3．将elem[i]插入(复制)到elem[j+1]的位置上。2．将elem[j+1..i-1]中的所有记录均后移一个位置；1．在elem[0..i-1]中查找elem[i]的插入位置，

elem[0..j]elem[i]<elem[j+1..i-1]；12elem012345211825221025*212125i=118221025*25i=218221025*2522212521151025*2521151025*2521181510181025*i=318i=51825*i=4插入排序过程演示13直接插入排序算法template<classElemType>voidStraightInsertSort(ElemType

elem[],intn)//操作结果:对数组elem作直接插入排序序{ for(inti=1;i<n;i++) { //第i趟直接插入排序

ElemTypee=elem[i]; //暂存elem[i]

intj; //临时变量

for(j=i-1;j>=0&&e<elem[j];j--) { //将比e大的计录都后移

elem[j+1]=elem[j]; //后移

}

elem[j+1]=e; //j+1为插入位置

}}14直接插入排序算法性能分析最好情况下（正序）：

e12345时间复杂度为O(n)。比较次数：n-1移动次数：2(n-1)123451234512345123452345二、插入排序InsertionSort15最坏情况下（逆序或反序）：e时间复杂度为O(n2)。54321453213452123451123454321比较次数：移动次数：2)1)(2(2-+=å=nnini2)1)(4(1-+=+ånnin2=i）（二、插入排序InsertionSort直接插入排序算法性能分析16平均情况下（随机排列）：

时间复杂度为O(n2)。比较次数：移动次数：4)1)(4(-+=ånnn2=i4)1)(2(2-+=å=nnnii2（21+i）二、插入排序InsertionSort直接插入排序算法性能分析17直接插入排序算法是一种稳定的排序算法。优缺点：直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。二、插入排序InsertionSort直接插入排序算法性能分析18如何改进直接插入排序?注意到，在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序，则在寻找插入位置时，可以用折半查找来代替顺序查找，从而较少比较次数。二、插入排序InsertionSort19排序过程：用折半查找方法确定插入位置的排序2、折半插入排序二、插入排序InsertionSort20i=0(30)1370853942620i=113(1330)70853942620i=66(6133039427085)20…...i=720(6133039427085)20lhmi=720(6133039427085)20lhmi=720(6133039427085)20lmhi=720(6133039427085)20lhi=720(613203039427085)折半插入排序过程21

3、2-路插入排序(略)4、表插入排序(略)在折半插入排序的基础上改进之二、插入排序InsertionSort22三、希尔排序

ShellSort又称缩小增量排序改进的着眼点：（1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高；（2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。

23（1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？（2）子序列内如何进行直接插入排序？需解决的关键问题?基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。三、希尔排序

ShellSort24基本有序：接近正序，例如{1,2,8,4,5,6,7,3,9}；局部有序：部分有序，例如{6,7,8,9,1,2,3,4,5}。局部有序不能提高直接插入排序算法的时间性能。分割待排序记录的目的?1.减少待排序记录个数；2.使整个序列向基本有序发展。子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。启示?三、希尔排序

ShellSort250123456784021254925*16初始序列300813d=44021254925*16300813252125*300849131640d=21325210825*16304940252125*300813164049d=10825211325*16304049082513162125*403049希尔插入排序过程26voidShellInsert(ElemType

elem[],intn,int

incr){ for(inti=incr;i<n;i++){

ElemTypee=elem[i];

intj;

for(j=i-incr;j>=0&&e<elem[j];j-=incr)

elem[j+incr]=elem[j];

elem[j+incr]=e;} }希尔插入排序算法27voidShellSort(ElemType

elem[],intn,intinc[],intt){ for(intk=0;k<t;k++){

ShellInsert(elem,n,inc[k]);}}希尔插入排序算法28解决方法：将相隔某个“增量”的记录组成一个子序列。增量应如何取？希尔最早提出的方法是d1=n/2，di+1=di/2。关键问题(1)应如何分割待排序记录？算法描述：for(k=0;k<t;k++){

以inc[k]为增量，进行组内直接插入排序；}三、希尔排序

ShellSort29关键问题(2)子序列内如何进行直接插入排序？for(i=incr;i<n;i++)//将elem[i]插入到所属的子序列中{e=elem[i];//暂存待插入记录

//j指向所属子序