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

1、主讲教师：章,英,数据结构与算法,2,第,21,讲,插入排序,本讲知识点,1,了解排序的相关基础知识,2,掌握插入排序、希尔排序的算法,难点,希尔排序,3,排序的基本概念,各种排序方法,各种排序方法的比较,排序知识体系结构,排序,插入排序,选择排序,交换排序,归并排序,基数排序,直接插入排序,折半插入排序,链表插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序,4,一、排序的定义,Sorting,排序的基本概念,假设含,n,个记录的序列为,R,1,R,2,R,n,其相应的关键字序列为,K,1,K,2,K,n,这些关键字相互之间可以进行比较，即在,它们之间存在着这样一个关系,K,p1,

2、K,p2,K,pn,按此固有关系将上式记录序列重新排列为,R,p1,R,p2,R,pn,的操作称作,排序,5,排序算法的稳定性,假定在待排序的记录集中，存在,多个具有相同键值的记录，若经过排序，这些记录的,相对次序,仍然保持不变，即在原序列中,k,i,k,j,且,r,i,在,r,j,之前，而在排序后的序列中,r,i,仍在,r,j,之前，则称这种,排序算法是稳定的；否则称为不稳定的,排序的基本概念,一、排序的定义,Sorting,学号,姓名,高数,英语,思想品德,0001,王,军,85,88,0002,李,明,64,92,0003,汤晓影,85,86,68,72,78,6,学号,姓名,高数,英语

3、,思想品德,0001,王,军,85,88,0002,李,明,64,92,0003,汤晓影,85,86,68,72,78,排序的基本概念,单键排序,根据一个关键码进行的排序,多键排序,根据多个关键码进行的排序,按学号排序单键排序,按成绩（高数英语思想品德）排序多键排序,一、排序的定义,Sorting,7,1,内排序,在排序的整个过程中，待排序的所有记录,全部被放置在内存中,2,外排序,由于待排序的记录个数太多，不能同时放,置在内存，而需要将一部分记录放置在内存，另一部,分记录放置在外存上，整个排序过程需要在内外存之,间多次交换数据才能得到排序的结果,排序的分类,外部排序,多路平衡归并、置换,选择

4、,一、排序的定义,Sorting,8,1,基于比较,基本操作,关键码的比较和记录的移动，其最差,时间下限已经被证明为,n,log,2,n,2,不基于比较,根据关键码的分布特征,基于比较的内排序,1,插入排序,2,交换排序,3,选择排序,4,归并排序,5,基数排序,排序的分类,一、排序的定义,Sorting,9,排序算法的性能,1,基本操作,内排序在排序过程中的基本操作,比较,关键码之间的比较,移动,记录从一个位置移动到另一个位置,2,辅助存储空间,辅助存储空间是指在数据规模一定的条件下，除了存,放待排序记录占用的存储空间之外，执行算法所需要,的其他存储空间,3,算法本身的复杂程度,一、排序的定

5、义,Sorting,10,1,直接插入排序,排序过程：整个排序过程为,n-1,趟插入，即先,将序列中第,1,个记录看成是一个有序子序列，然,后从第,2,个记录开始，逐个进行插入，直至整个,序列有序,基本思想：在插入第,i,i,1,个记录时，前,面的,i-1,个记录已经排好序,二、插入排序,Insertion Sort,11,有序序列,elem0.i-1,elemi,无序序列,elemi.n-1,一趟直接插入排序的基本思想,有序序列,elem0.i,无序序列,elemi+1.n-1,12,实现“一趟插入排序”可分三步进行,3,将,elemi,插入,复制,到,elemj+1,的位置上,2,将,el

6、emj+1.i-1,中的所有,记录,均,后移,一个位置,1,在,elem0.i-1,中,查找,elemi,的插入,位置,elem0.j,elemi elemj+1.i-1,13,elem 0 1 2 3 4 5,21,18,25,22,10,25,21,21,25,i,1,18,22,10,25,25,i,2,18,22,10,25,25,22,21,25,21,15,10,25,25,21,15,10,25,25,21,18,15,10,18,10,25,i,3,18,i,5,18,25,i,4,插入排序过程演示,14,直接插入排序算法,template,void StraightInser

7、tSort(ElemType elem, int n,操作结果,对数组,elem,作直接插入排序序,for ( int i = 1; i n; i,第,i,趟直接插入排序,ElemType e = elemi,暂存,elemi,int j,临时变量,for (j = i,1; j = 0 j,将比,e,大的计录都后移,elemj + 1 = elemj,后移,elemj + 1 = e,j+1,为插入位置,15,直接插入排序算法性能分析,最好,情况下（正序,e,1,2,3,4,5,时间复杂度为,O,n,比较次数,n,1,移动次数,2,n,1,1,2,3,4,5,1,2,3,4,5,1,2,3,

8、4,5,1,2,3,4,5,2,3,4,5,二、插入排序,Insertion Sort,16,最坏,情况下（逆序或反序,e,时间复杂度为,O,n,2,5,4,3,2,1,4,5,3,2,1,3,4,5,2,1,2,3,4,5,1,1,2,3,4,5,4,3,2,1,比较次数,移动次数,2,1,2,2,n,n,i,n,i,2,1,4,1,n,n,i,n,2,i,二、插入排序,Insertion Sort,直接插入排序算法性能分析,17,平均,情况下（随机排列,时间复杂度为,O,n,2,比较次数,移动次数,4,1,4,n,n,n,2,i,4,1,2,2,n,n,n,i,i,2,2,1,i,二、插入

9、排序,Insertion Sort,直接插入排序算法性能分析,18,直接插入排序算法是一种,稳定,的排序算法,优缺点,直接插入排序算法简单、容易实现，适用于待排,序记录基本有序或待排序记录较小时,当待排序的记录个数较多时，大量的比较和移动,操作使直接插入排序算法的效率降低,二、插入排序,Insertion Sort,直接插入排序算法性能分析,19,如何改进直接插入排序,注意到，在插入第,i,i,1,个记录时，前面的,i,1,个,记录已经排好序，则在寻找插入位置时，可以用折,半查找来代替顺序查找，从而较少比较次数,二、插入排序,Insertion Sort,20,排序过程：用折半查找方法确定插入

10、位置的排序,2,折半插入排序,二、插入排序,Insertion Sort,21,i=0 (30) 13 70 85 39 42 6 20,i=1,13,13 30) 70 85 39 42 6 20,i=6,6,6 13 30 39 42 70 85) 20,i=7,20,6 13 30 39 42 70 85) 20,l,h,m,i=7,20,6 13 30 39 42 70 85) 20,l,h,m,i=7,20,6 13 30 39 42 70 85) 20,lmh,i=7,20,6 13 30 39 42 70 85) 20,l,h,i=7,20,6 13 20 30 39 42 70

11、 85,折半插入排序过程,22,3,2,路插入排序,略,4,表插入排序,略,在折半插入排序的基础上改进之,二、插入排序,Insertion Sort,23,三、希尔排序,Shell Sort,又称缩小增量排序,改进的着眼点,1,若待排序记录按关键码,基本有序,时，直接插入,排序的效率可以大大提高,2,由于直接插入排序算法简单，则在待排序记录,数量,n,较小,时效率也很高,24,1,应如何分割待排序记录，才能保证整个序列逐步,向基本有序发展,2,子序列内如何进行直接插入排序,需解决的关键问题,基本思想,将整个待排序记录,分割,成若干个子序列,在子序列内分别进行直接插入排序，待整个序列中的,记录,

12、基本有序,时，对全体记录进行直接插入排序,三、希尔排序,Shell Sort,25,基本有序,接近正序，例如,1, 2, 8, 4, 5, 6, 7, 3, 9,局部有序,部分有序，例如,6, 7, 8, 9, 1, 2, 3, 4, 5,局部有序不能提高直接插入排序算法的时间性能,分割待排序记录的目的,1,减少待排序记录个数,2,使整个序列向基本有序发展,子序列的构成不能是简单地“逐段分割”，而是将相,距某个“增量”的记录组成一个子序列,启示,三、希尔排序,Shell Sort,26,0 1 2 3 4 5 6 7 8,40,21,25,49,25,16,初始序列,30,08,13,d =

13、4,40,21,25,49,25,16,30,08,13,25,21,25,30,08,49,13,16,40,d = 2,13,25,21,08,25,16,30,49,40,25,21,25,30,08,13,16,40,49,d = 1,08,25,21,13,25,16,30,40,49,08,25,13,16,21,25,40,30,49,希尔插入排序过程,27,void ShellInsert(ElemType elem, int n, int incr,for ( int i = incr; i n; i,ElemType e=elemi,int j,for(j=i-incr;j

14、=0 j-=incr,elemj+incr=elemj,elemj+incr=e,希尔插入排序算法,28,void ShellSort(ElemType elem, int n, int inc, int,t,for ( int k = 0; kt; k,ShellInsert(elem, n, inck,希尔插入排序算法,29,解决方法,将相隔某个“增量”的记录组成一个子序列,增量应如何取,希尔最早提出的方法是,d,1,n/2,d,i+1,d,i,2,关键问题,1,应如何分割待排序记录,算法描述,for (k=0; kt; k,以,inck,为增量，进行组内直接插入排序,三、希尔排序,She

15、ll Sort,30,关键问题,2,子序列内如何进行直接插入排序,for,i=incr,in,i,将,elemi,插入到所属的子序列中,e=elemi,暂存待插入记录,j,指向所属子序列的最后一个记录,for,j=i-incr,j=0,eelemj,j-=incr,elemj+incr=elemj,记录后移,d,个位置,然后,j-incr,比较同一子序列的前一个记录,elemj+incr=e,三、希尔排序,Shell Sort,31,希尔排序特点,子序列的构成不是简单的“逐段分割,而是将相隔某个增量的记录组成一个子序,列,希尔排序可提高排序速度,因为,分组后,n,值减小,n2,更小，而,T(n)=O(n2,所以,T(n,从总