数据结构-从概念到C++实现（第4版）课件 7-2插入排序

7-2插入排序v第七章排序技术学什么？直接插入排序希尔排序提出关键问题给出解决方法写出算法描述得到完整算法运行实例7-2-1直接插入排序v第七章排序技术基本思想在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序有序区r1r2ri-1……无序区rirnri+1……r'1r'2r'i-1r'i……rnri+1……直接插入排序的基本思想：依次将待排序序列中的每一个记录插入到已排好序的序列中，直到全部记录都排好序。运行实例2420101812122420101812242010181224201018122420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果如何构造初始的有序序列？242010181212待排序序列for(i=1;i<length;i++){

}将第1个记录看成是初始有序序列，然后从第2个记录起依次插入到有序序列中，直至将第n个记录插入。解决方法：算法描述：插入第i个记录，即第i趟直接插入排序；关键问题如何将第i

个记录插入到有序序列中的合适位置？第一趟排序结果24201018122010182412242010181212待排序序列关键问题242010181212242010181224待排序序列第一趟排序结果第二趟排序结果i在有序序列中进行顺序查找，查找下标初始化为多少？jj=i-1;暂存r[i]关键问题2420101812122420101812241012待排序序列第一趟排序结果第二趟排序结果i在有序序列中进行顺序查找，循环条件是什么？temp=data[i];j=i-1;退出循环，记录r[i]的最终位置是哪里？data[j+1]=temp;算法描述：while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}j关键问题暂存r[i]算法描述voidSort::InsertSort(){ inti,j,temp;for(i=1;i<length;i++){temp=data[i];j=i-1;while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}data[j+1]=temp; }}时间性能比较语句？执行次数？最好情况：n-1次12345最坏情况：2+3+…+n次12345移动语句？执行次数？最好情况：2(n-1)次12345voidSort::InsertSort(){ inti,j,temp;for(i=1;i<length;i++){temp=data[i];j=i-1;while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}data[j+1]=temp; }}最坏情况：3+4+…+n+1次12345时间性能时间性能比较次数：n-1移动次数：2(n-1)

最好情况：正序O(n)最坏情况：逆序比较次数：移动次数：平均情况：随机排列O(n2)O(n2)空间性能时间性能

空间性能：O(1)

稳定性：稳定125*454125*455*125*45while(temp<data[j]){data[j+1]=data[j];j--;}7-2-2希尔排序v第七章排序技术改进的着眼点在待排序序列正序时，直接插入排序的时间性能是O(n)。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。（1）若待排序记录按关键码基本有序，直接插入排序的效率较高；改进的着眼点：（2）若待排序记录数量

n

较小，直接插入排序的效率也很高。待排序记录数量n

较大、并不是按关键码基本有序，怎么办？基本思想希尔排序的基本思想：将待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序，待序列基本有序时，对全体记录进行直接插入排序。局部有序（部分有序）不能提高直接插入排序算法的时间性能。基本有序：接近正序，例如{1,2,8,4,5,6,7,3,9}。{5,6,7,8,9,1,2,3,4}是基本有序吗？如何分割待排序序列，才能使整个序列逐步向基本有序发展？如何分割待排序序列，才能使整个序列逐步向基本有序发展？不能是逐段分割，而是将相距某个增量的记录组成一个子序列2408321024*162028123024321624*100812202830基本思想运行实例081024*28321612242030待排序序列增量d=4321612242030081024*28增量d=2321612081024203024*2824203024*2832161008123216120824203024*2810增量d=1关键问题希尔排序的基本思想：将待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序，待序列基本有序时，对全体记录进行直接插入排序。如何分割待排序序列，才能使整个序列逐步向基本有序发展？（1）希尔排序的时间性能取决于增量序列，复杂的数学问题。（2）希尔排序是平均时间性能好于O(n2)的第一批算法之一（1959年）。（3）希尔最早提出的方法是，且增量序列互质。显然最后一个增量必须等于1——缩小增量排序算法效率与增量序列密切相关，练习中一般会给定增量序列for(d=length/2;d>=1;d=d/2){

}算法描述：以d为增量，在每个子序列内进行直接插入排序；关键问题希尔排序的基本思想：将待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序，待序列基本有序时，对全体记录进行直接插入排序。如何分割待排序序列，才能使整个序列逐步向基本有序发展？关键问题081024*28321612242030待排序序列增量d=4081024*28321612242030i在一趟希尔排序中，从哪个记录开始执行插入操作？for(i=d+1;i<length;i++){

}算法描述：将r[i]插入到所属子序列的合适位置；081024*28321612242030待排序序列增量d=4081024*28321612242030ij在相应子序列中进行顺序查找，查找下标初始化为多少？循环条件是什么？1632算法描述：temp=r[i];j=i-

d; while(j>=0&&temp<data[j]){data[j+d]=data[j];j=j-d;}关键问题081024*28321612242030待排序序列增量d=4081024*28321612242030ij1632退出循环，记录r[i]的最终位置是哪里？data[j+d]=temp;16算法描述：temp=r[i];j=i-

d; while(j>=0&&temp<data[j]){data[j+d]=data[j];j=j-d;}关键问题验证算法081024*28321612242030待排序序列增量d=4081024*28321612242030ij203216081024*2812242030242032081024*281230直接插入排序时间性能较好分割使得子序列的记录个数较少16算法实现voidSort::ShellSort(){ intd,i,j,temp;for(d=length/2;d>=1;d=d/2)//增量为d进行直接插入排序{for(i=d;i<length;i++)//进行一趟希尔排序{temp=data[i];//暂存待插入记录for(j=i-d;j>=0&&temp<data[j];j=j-d)data[j+d]=data[j];//记录后移d个位置data[j+d]=temp;}}}性能分析（1）希尔排序算法的时间性能是所取增量的函数；

时间性