《排序技术》ppt课件

《《排序技术》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章排序技术本章的基本内容是：插入排序交换排序选择排序归并排序插入排序插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。直接插入排序插入排序有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。（1）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置?直接插入排序插入排序需解决的关键问

2、题?直接插入排序过程示例r0123456211825221025*212125插入排序i=218221025*25i=318221025*2225222110252115102525*2521151025*252118151018181025*i=418i=61825*i=5r[0]的作用?暂存单元监视哨解决方法：将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。插入排序关键问题(1)如何构造初始的有序序列？算法描述：for(i=2;i<=n;i++){插入第i个记录，即第i趟直接插入排序；}关键问题(2)如何查找待插入记

3、录的插入位置?解决方法：在i-1个记录的有序区r[1]~r[i-1]中插入记录r[i]，首先顺序查找r[i]的正确插入位置，然后将r[i]插入到相应位置。r[0]有两个作用：1.进入循环之前暂存了r[i]的值，使得不致于因记录的后移而丢失r[i]的内容；2.在查找插入位置的循环中充当哨兵。插入排序算法描述：r[0]=r[i];j=i-1;while(r[0]

4、+1]=r[j];j=j-1;}r[j+1]=r[0];}}直接插入排序算法插入排序如果r[i]>=r[i-1]，内层循环会出现什么情况?直接插入排序算法性能分析最好情况下（正序）：插入排序12345时间复杂度为O(n)。比较次数：n-1移动次数：2(n-1)123451234512345123452345直接插入排序算法性能分析插入排序最好情况下（正序）：比较次数：n-1移动次数：2(n-1)最坏情况下（逆序或反序）：时间复杂度为O(n2)。54321453213452123451123454321比较次数：移动次数：2)1)(2(2-+=å=nnini2)1)(

5、4(1-+=+ånnin2=i）（时间复杂度为O(n)。平均情况下（随机排列）：直接插入排序算法性能分析插入排序时间复杂度为O(n2)。比较次数：移动次数：4)1)(4(-+=ånnn2=i4)1)(2(2-+=å=nnnii2（21+i）空间性能：需要一个记录的辅助空间。直接插入排序算法是一种稳定的排序算法。直接插入排序算法性能分析插入排序直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。希尔排序改进的着眼点：（1）若待排序记录按关键码基本有序时，直接插入排序的效

6、率可以大大提高；（2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。插入排序（1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？（2）子序列内如何进行直接插入排序？插入排序需解决的关键问题?基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。希尔排序希尔插入排序过程示例1234567894021254925*16初始序列插入排序300813d=44021254925*16300813252125*300849131640d=21325210825*163

7、04940252125*300813164049d=10825211325*16304049082513162125*403049算法描述：for(i=d+1;i<=n;i++)//将r[i]插入到所属的子序列中{r[0]=r[i];//暂存待插入记录j=i-d;//j指向所属子序列的最后一个记录while(j>0&&r[0]