第10章内部排序.ppt

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

1、第10章内部排序2021/7/16主要内容概述1插入排序2快速排序3选择排序4基数排序6各种内部排序方法的比较讨论7归并排序52021/7/16DS10.1概述排序定义：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序排序的目的：便于查找排序算法的好坏如何衡量时间效率：排序速度（即排序所花费的全部比较次数）空间效率：占内存辅助空间的大小稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。2021/7/16DS10.1概述排序分类按待排序记录所在位置内部排序：待排序记录

2、存放在内存外部排序：排序过程中需对外存进行访问的排序注：外部排序时，要将数据分批调入内存来排序，中间结果应及时放入外存，显然外部排序要复杂得多按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序2021/7/16DS10.1概述按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(logn)基数排序：T(n)=O(d.n)排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置2021/7/16DS10.1概述

3、待排记录的数据类型设为：#defineMAXSIZE20//小顺序表的最大长度typedefintKeyType;//设关键字为整型量（int型）Typedefstruct{//定义每个记录（数据元素）的结构KeyTypekey;//关键字InfoTypeotherinfo;//其它数据项}RedType;typedefstruct{//定义顺序表的结构RedTyper[MAXSIZE+1];//存储顺序表的向量//r[0]一般作哨兵或缓冲区intlength;//顺序表的长度}SqList;2021/7/16DS10.2插入排序插入排序的

4、基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。插入排序有多种具体实现算法：直接插入排序折半插入排序希尔排序2021/7/16DS10.2插入排序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序算法描述2021/7/16DS10.2插入排序例49386597761327i=238(3849)6597761327i=365(38

5、4965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：2021/7/16DS10.2插入排序算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：2021

6、/7/16DS10.2插入排序折半插入排序排序过程：用折半查找方法确定插入位置的排序例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)2021/7/16DS10.2插入排序希尔排序(缩小增量法)排序过程：先取一个正整数d

7、1

8、6DS10.2插入排序voidShellInsert(SqList&L，intdk){for(i=dk+1；i<=L.length；++i)if(L.r[i].key