《数据结构排序》课件

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

1、第10章排序陈守孔孟佳娜陈卓1本章目录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磁带排序2主要内容知识点1、排序的定义，排序可以看作是线性表的一种操

2、作2、排序的分类，稳定排序与不稳定排序的定义。3、插入排序（直接插入、对分插入、二路插入、表插入、希尔插入排序）。4、交换排序（冒泡排序、快速排序）。5、选择排序（简单选择排序、树形选择排序、堆排序）。6、归并排序、基数排序。7、外部排序重点难点1、各种排序所基于的基本思想。2、排序性能的分析，是否是稳定排序。3、折半插入、希尔排序。4、快速排序。5、堆排序。6、败者树、置换选择排序、最佳归并树。7、对每种排序方法的学习，能举一反三。3基本概念排序：假设含n个记录的序列为{R1,R2,…,Rn}，其相应的关键字序列为{K1,K2,…,Kn}，这些关键字相互之间可以进行比较，即在它们之

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

4、ntkey;AnyTypeother;∥记录其它数据域}RecType;RecTypeR[n+1];6基本思想：假定第一个记录有序，从第2个记录开始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。插入排序插入排序种类：直接插入排序折半插入排序二路插入排序表插入排序希尔排序7直接插入排序基本思想：将记录R[i](2<=i<=n)插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]8示例初始关键字序列：[51]33629687172851'i=2(33)[3351]629687172851'i=3(62)[335

5、162]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]9一趟直接插入排序算法voidStrOnePass(RecTypeR[]，inti){∥已知R[1..i-1]中的记录按关键字非递减有序排列，本算法∥插入R[i],使R[1..i]中的记录按关键字非递减有序排列R[0]=R[i];j=i-1;∥将待排序记录放进监视哨x=R[0].key;∥从后向前

6、查找插入位置，将大于待排序记录向后移动while(x

7、sSort(RecTypeR[]，intn)∥对R[1..n]进行折半插入排序{for(i=2;i<=n;i++)∥假定第一个记录有序{R[0]=R[i];∥将待排记录R[i]暂存到R[0]low=1;high=i-1;∥设置折半查找的范围R[low..high]while(low<=high){m=(low+high)/2;∥折半if(R[0].key