数据结构第10章排序课件.ppt

《数据结构第10章排序课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DATASTRUCTURE2021/7/281第10章排序2021/7/282本章目录10.1概述10.2插入排序10.2.1直接插入排序10.2.2折半插入排序*10.2.3二路插入排序*10.2.4表插入排序10.2.5希尔排序10.3交换排序10.3.1起泡排序10.3.2快速排序10.4选择排序10.4.1直接选择排序10.4.2树形选择排序10.4.3堆排序10.5归并排序10.6分配排序10.7内部排序方法的比较10.8外部排序10.8.1文件管理10.8.2外部排序10.8.3多路归并排序10.8.4置换选择排序*10.8.5最佳归并树*10.8.6磁带排序202

2、1/7/283主要内容知识点1、排序的定义，排序可以看作是线性表的一种操作2、排序的分类，稳定排序与不稳定排序的定义。3、插入排序（直接插入、对分插入、二路插入、表插入、希尔插入排序）。4、交换排序（冒泡排序、快速排序）。5、选择排序（简单选择排序、树形选择排序、堆排序）。6、归并排序、基数排序。7、外部排序重点难点1、各种排序所基于的基本思想。2、排序性能的分析，是否是稳定排序。3、折半插入、希尔排序。4、快速排序。5、堆排序。6、败者树、置换选择排序、最佳归并树。7、对每种排序方法的学习，能举一反三。2021/7/284基本概念排序：假设含n个记录的序列为{R1,R2,…,

3、Rn}，其相应的关键字序列为{K1,K2,…,Kn}，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1≤Ks2≤…≤Ksn，按此固有关系将n个记录的序列重新排列为{Rs1,Rs2,…,Rsn}的操作称作排序。2021/7/285基本概念稳定排序：若Ki为关键字，Ki=Kj（i≠j），且在排序前的序列中Ri领先于Rj。经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的。内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能一

4、次在内存中完成，则称此类排序问题为外部排序2021/7/286排序的类型定义#definen待排序记录的个数typedefstruct{intkey;AnyTypeother;∥记录其它数据域}RecType;RecTypeR[n+1];2021/7/287基本思想：假定第一个记录有序，从第2个记录开始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。插入排序插入排序种类：直接插入排序折半插入排序二路插入排序表插入排序希尔排序2021/7/288直接插入排序基本思想：将记录R[i](2<=i<=n)插入到有序子序列R[1..i-1]中，使记录的

5、有序序列从R[1..i-1]变为R[1..i]2021/7/289示例初始关键字序列：[51]33629687172851'i=2(33)[3351]629687172851'i=3(62)[335162]9687172851'i=4(96)[33516296]87172851'i=5(87)[3351628796]172851'i=6(17)[173351628796]2851'i=7(28)[17283351628796]51'i=8(51')[1728335151'628796]2021/7/2810一趟直接插入排序算法voidStrOnePass(RecTypeR[]，

6、inti){∥已知R[1..i-1]中的记录按关键字非递减有序排列，本算法∥插入R[i],使R[1..i]中的记录按关键字非递减有序排列R[0]=R[i];j=i-1;∥将待排序记录放进监视哨x=R[0].key;∥从后向前查找插入位置，将大于待排序记录向后移动while(x

7、;i++)∥假定第一个记录有序StrOnePass(R，i)；}2021/7/2812直接插入排序性能分析最坏情况比较次数为=(n+2)(n-1)/2移动次数为=(n+4)(n-1)/2最好情况比较次数为n-1次移动次数为2（n-1）次2021/7/2813直接插入排序的优缺点直接插入排序算法简单，当待排序记录数量n很小时，局部有序时，较为适用。当n很大时，其效率不高。若对直接插入排序算法进行改进，可从减少“比较”和“移动”次数这两方面着手。折半存入排序、二路插入排序、表插入排序、希尔排序都