各种排序算法分析ppt课件.ppt

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

1、排序算法及算法分析1问题的提出：为什么要排序？有序表的优点？缺点？构造关系。按照什么原则排序？比较？如何进行排序？2基本概念排序（Sorting）：简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）学号姓名年龄性别2019001张佳18男2019002王鹏19男2019003刘宁17女2019004李娟18女2019005陈涛19男2019006李小燕18女3作为比较基础的一个(或多个)字段，称为排序码。排序码可以是数值、符号或符号串。排序码不一定是关键码，关

2、键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。参与排序的对象，称为记录。一个记录可以包含多个字段。如果记录集合中存在多个排序码相同的记录，经过排序后，排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定的，否则是不稳定的。排序码与关键码（primarykey）4排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外

3、排序。排序的类型5排序算法的评价评价排序算法好坏的标准执行算法所需的时间执行算法所需要的附加空间算法本身的复杂程度也是考虑的一个因素排序的时间开销是算法好坏的最重要的标志排序的时间开销衡量标准:算法执行中的比较次数（必须）。算法执行中的移动次数（有可能避免）。通常会关注最坏情况和平均情况的开销。6插入排序基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。x顺次选取一个元素插入到合适位置7插入排序的细分类如何插入到已排好序的序列中？直接插入（从后向前找位置后插入）O(n2)二分法插入（按二分

4、法找位置后插入）O(nlog2n)表插入排序（按链表查找位置后插入）O(n2)8直接插入排序基本思想：假定前面m个元素已经排序；取第(m+1)个元素，插入到前面的适当位置；一直重复，到m=n为止。（初始情况下，m=1）9第一趟：{23}，[起始只有一个记录]{11,23}11第二趟：{11，23}，{11，23，55}55第三趟：{11，23，55}，{11，23，55，97}97第四趟：{11，23，55，97}，{11，19，23，55，97}19第五趟：{11，19，23，55，97}，{11，19，23，55，80，97}80示例：{23

5、，11，55，97，19，80}10直接插入排序的算法中记录的数据结构typedefintKeyType;typedefintDataType;typedefstruct{KeyTypekey;/*排序码字段*/DataTypeinfo;/*记录的其他字段*/}RecordNode;typedefstruct{intn;/*n为文件中的记录个数，n

6、接插入排序算法评价2最小移动次数∶最大移动次数∶13直接插入排序算法评价3初始数据状态相关：文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则算法的时间复杂度为O(n)若初态为反序，则时间复杂度为O(n2)14直接插入排序算法评价4——平均复杂度插入记录Ri-1，有i种可能的插入位置，即插入到第0，1，…，i-1位置上，假设每种情况发生的概率是相等的，均为pj=1/i(j=0,1,…,i-1)比较次数为Cj=j+1(j=0,…,i-2,i-2)，则插入记录Ri-1的平均比较次数为∶15直接插入排序算法评价5——平均复杂度直接

7、插入排序的总的比较次数为：16直接插入排序算法评价直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)直接插入排序的平均时间复杂度为T(n)=O(n2)算法中引入了一个附加的记录空间temp，因此辅助空间为S(n)=O(1)直接插入排序是稳定的17存储结构与算法优化顺序存储结构：二分插入算法，减少比较次数。链式存储结构：减少移动次数。18二分法插入排序特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序限制：必须采用顺序存储方式。19例：有6个记录，前5个已排序的基础上，对第6个记录

8、排序。[1527365369]42lowmidhigh[1527365369]42lowhighmid[1527365369