资源描述：
《张乃孝全套配套课件算法与数据结构 第8章 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八章排序目录8.1基本概念8.2插入排序8.2.1直接插入排序8.2.2二分法插入排序8.2.3表插入排序8.2.4Shell排序8.3选择排序8.3.1直接选择排序8.3.2堆排序8.4交换排序8.4.1起泡排序8.4.2快速排序8.5分配排序8.5.1概述8.5.2基数排序8.6归并排序8.6.1内排序8.6.2外排序*8.1基本概念排序的对象是由一组记录组成的文件，每个记录由若干字段组成，所谓排序码是记录中的一个(或多个)字段，排序以排序码为依据。排序码可以不是关键码，则可能有多个记录具有相同的排序码，
2、使得排序的结果不唯一。排序码之间需要进行比较，本章中都假设排序码为整型。设{R0,R1,…,Rn-1}是由n个记录组成的文件，{K0,K1,…,Kn-1}是排序码集合，所谓排序就是将文件中的全部记录按排序码不增(或不减)的次序重新排列。排序看成字典上的操作在排序的讨论中，并不关心被排序对象本身的逻辑结构，所以读者可以把排序看成是字典上的一种操作。不同的排序算法，可能依赖与不同的存储结构，可以理解为在字典的不同存储表示上排序的实现。而把非字典结构中元素的排序，归结为是对于其结点按照排序码建立的密集索引的排序。与上
3、一章关于索引的讨论类似，在本章的具体排序算法中，只关心排序码的作用和表示，而把记录中的其它字典隐藏起来。在待排序的文件中，如果存在多个排序码相同的记录，经过排序后，相同排序码记录的相对次序如果保持不变，则称这种排序方法是稳定的，否则是不稳定的。稳定性本章中提到的记录和文件，主要是指内存的数据。待排序的记录在排序过程中全部存放在内存的称为内排序，否则称为外排序。外排序也就是外存文件的排序。本章讨论的主要是内排序的方法，但有些方法(例如归并排序)也适用于外排序。内排序与外排序排序方法分类插入排序、选择排序、交换排序
4、、分配排序、归并排序。（每一种方法具体可能有多个不同算法）评价排序算法代价的标准第一，执行算法所需的时间；比较次数、移动次数第二，执行算法所需要的附加空间；另外，算法本身的复杂程度也是比较算法一个因素。8.2插入排序基本方法是∶每步将一个待排序的记录，按其排序码大小，插到前面已经排序的文件中的适当位置，直到全部插入完为止。直接插入排序二分法插入排序表插入排序shell排序8.2.1直接插入排序假设待排序的n个记录{R0,R1,…,Rn-1}顺序存放在数组中，直接插入法在插入记录Ri(i=1,2…n-1)时，记录
5、集合被划分为两个区间[R0，Ri-1]和[Ri，Rn-1]，其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将排序码Ki与Ki-1，Ki-2，…，K0依次比较，找出应该插入的位置，将记录Ri插入。直接插入排序采用顺序存储结构。例题设待排序的记录共8个，排序码分别为49,38,65,97,76,13,27,49’，请用直接插入排序法排序(为了区别两个相同的排序码49，后面的49用49’表示)。初始序列∶[49]38659776132749’ i=1∶[3849]659776132749’ i=2∶[
6、384965]9776132749’ i=3∶[38496597]76132749’ i=4∶[3849657697]132749’ i=5∶[133849657697]2749’ i=6∶[13273849657697]49’ i=7∶[1327384949’657697]typedefintKeyType;typedefintDataType;typedefstruct{KeyTypekey;/*排序码字段*/DataTypeinfo;/*记录的其它字段*/}RecordNode;typedefstruct
7、{intn;/*n为文件中的记录个数*/RecordNode*record;}SortObject;存储结构程序实现：voidinsertSort(SortObject*pvector)若文件初态为正序，则算法的时间复杂度为O(n)，若初态为反序，则时间复杂度为O(n2)。平均移动次数与平均比较次数同级，是O(n2)。直接插入排序的平均时间复杂度为T(n)=O(n2)。算法中引入了一个附加的记录空间temp，因此辅助空间为S(n)=O(1)。直接插入排序是稳定的。算法的设计与分析8.2.2二分法插入排序在直接插
8、入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序。(1)[13273849657697]49’(2)13273849[657697]49’(3)13273849[65]769749’(4)1327384949’657697二分法插入排序示例二分法插入排序必须采用顺序存储方式，存储结构的定义同上一节的SortObject。程序实现存储结构与算法代
