数据结构 C语言版 教学课件 作者 严蔚敏 李冬梅 吴伟民 第8章 排序.ppt

《数据结构 C语言版 教学课件 作者 严蔚敏 李冬梅 吴伟民 第8章 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2021年7月22日北京林业大学信息学院李冬梅数据结构2021年7月22日北京林业大学信息学院2021年7月22日北京林业大学信息学院第8章　排序教学内容8.1概述8.2插入排序8.3交换排序8.4选择排序8.5归并排序21254925*16082021年7月22日北京林业大学信息学院1.掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用2.熟练掌握直接插入排序、折半插入排序、起泡排序、直接选择排序、快速排序的排序算法及其性能分析3.掌握希尔排序、归并排序、堆排序、基数排序的方法及其性能分析教学目标2021年7月22日北京林业大学信息学院8

2、.1概述1.什么是排序？将一组杂乱无章的数据按一定规律顺次排列起来。2.排序的目的是什么？存放在数据表中按关键字排序——便于查找！2021年7月22日北京林业大学信息学院3.什么叫内部排序？什么叫外部排序？若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。2021年7月22日北京林业大学信息学院4.排序算法的好坏如何衡量？时间效率——排序速度（比较次数与移动次数）空间效率——占内存辅助空间的大小稳定性——A和B

3、的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。2021年7月22日北京林业大学信息学院记录序列以顺序表存储Typedefstruct{//定义每个记录（数据元素）的结构KeyTypekey;//关键字InfoTypeotherinfo;//其它数据项}RedType;Typedefstruct{//定义顺序表的结构RedTyper[MAXSIZE+1];//存储顺序表的向量//r[0]一般作哨兵或缓冲区intlength;//顺序表的长度}SqList;#defineMAXSIZE20//设记录不超过20个typedef

4、intKeyType;//设关键字为整型量（int型）2021年7月22日北京林业大学信息学院排序算法分类规则不同插入排序交换排序选择排序归并排序时间复杂度不同简单排序O(n2)先进排序O(nlog2n)2021年7月22日北京林业大学信息学院8.2插入排序基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的2021年7月22日北京林业大学信息学院插入排序算法分类直接插入排序折半插入排序希尔排序最简单的排序法！2021年7月22日北京林业大

5、学信息学院直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】例（13，6，3，31，9，27，5，11）2021年7月

6、22日北京林业大学信息学院21254925*16080123456暂存21i=2i=3i=5i=4i=62525494925*25*49161625*08084921254925*21初态：164925*25211608完成!将序列存入顺序表L中，将L.r[0]作为哨兵（21，25，49，25*，16，08）*表示后一个252021年7月22日北京林业大学信息学院直接插入排序voidInsertSort(SqList＆L){inti,j;for(i=2;i<=L.length;++i)if(L.r[i].key

7、.r[i]插入有序子表{L.r[0]=L.r[i];//复制为哨兵L.r[i]=L.r[i-1];for(j=i-2;L.r[0].key

8、key)2021年7月22日北京林业大学信息学院最坏情况下：第i趟比较i次，移动i+1次21254925*1608算法分析比较次数移动次