《数据结构与算法 (16).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法 (16).pdf（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 线性表的查找与排序6.1 查找问题 6.2 排序问题 排序：是将一组具有相同数据类型的数据元素调整为按关键字从小到大或从大到小排列的过程。【例】按成绩对学生成绩表排序:成绩成绩性别性别姓名姓名准考证号准考证号数据项数据项记记录录关键项关键项6.2.1 排序的基本概念3 3 排序方法的稳定和不稳定张三 80分李四 75分王五 85分陈六 90分李四 75分张三 80分王五 85分陈六 90分陈六 90分王五 85分张三 80分李四 75分当需要排序的关键字取值都不相同时,排序的结果是唯一的4 4当排序的关键字中存在相同的情况时,排序方法不唯一;张三 80分李四 75分王五 85分陈六 8
2、0分李四 75分张三 80分陈六 80分王五 85分李四 75分陈六 80分张三 80分王五 85分在排序前后，含相等关键字的记录的相对位置保持不变，称这种排序方法是稳定的；反之，含相等关键字的记录的相对位置有可能改变，称这种排序方法是不稳定的。5 5 内部排序和外部排序排序期间文件的全部记录不能同时存放在计算机的内存中，要借助计算机的外存才能完成排序，称之为“外部排序”。在排序过程中，只使用计算机的内存存放待排序记录，称这种排序为内部排序。6 6 排序算法的评价和分类时间复杂度、空间复杂度稳定性：稳定，不稳定内部排序和外部排序7 7#define MAXSIZE 1000typedef st
3、ruct KeyType key；/key为关键字OtherType otherdata；RecordType；/数据元素的类型typedef struct RecordType rMAXSIZE+1 /r0为工作单元或闲置int length；/length为顺序表的长度SqList；/顺序表类型 顺序表的类型定义：6.2.2 线性表的插入排序 6.2.2.1 直接插入排序6.2.2.2 希尔排序1010 直接插入排序：就是一趟一个地将待排序记录插入到已经排好序的部分记录的适当位置中，使其成为一个新的有序序列，直到所有待排序记录全部插入完毕。即：将整个数据表看作左右两部分；其中左边为有序区，
4、右边为无序区；整个排序的过程就是将右边元素逐个插入到左边，以构成更大的有序区。直接插入排序算法思想1111 直接插入排序的过程：从第二个记录开始，也就是说：将第1个记录视为已排好序的集合(有序区)，然后将第2个记录插入到该集合中。即：i从2循环到n，即可实现完整的直接插入排序。假设待排序记录存放在rn+1之中，为了提高效率，附设一个监视哨r0，用于存放待插入的记录，并具有防止数组下标越界的作用。初始状态下：r1为有序区。1212初始关键字初始关键字:4949386565979776761313272749494949383849383849656538384965659797383849656
5、57676979713383849656576769797132738384965657676979713273838494949656576769797L.r0L.r0 L.r0L.r0 L.r0L.r0L.r0L.r0 L.r0L.r0 L.r0L.r0 L.r0L.r0直接插入排序过程直接插入排序过程【例】(1)备份待插入的记录，以便前面关键字较大的记录后移；(2)防止下标越界。监视哨L.r013131.void InsertionSort(SqList&L)2./对顺序表对顺序表 L 作直接插入排序。作直接插入排序。3.for(i=2;i=L.length;+i)4.if(L.ri.k
6、ey L.ri-1.key)5.L.r0=L.ri;/复制为监视哨复制为监视哨6.for(j=i-1;L.r0.key ri-1.key，待排序记录本身已按关键字有序排列,for循环只执行1次，且不移动记录，此时总的比较次数为n-1次。15151616直接插入排序算法分析(续）(1)稳定性直接插入排序是稳定的排序方法。(2)算法效率a.时间复杂度 T(n)最好情况:比较：O(n),移动O(1);最坏情况:比较：O(n2),移动O(n2);平均：O(n2)b.空间复杂度S(n)：O(1)。取决于数据的初始分布17176.2.2 线性表的插入排序6.2.2.1 直接插入排序 6.2.2.2 希尔排
7、序1818希尔排序-by Donald Shell 基本思想：先将数据表调整为基本有序，然后再作插入排序。调整为基本有序的方法：选择一个步长d，将元素下标之差为d 的倍数的元素放在一组，在每组内作插入排序。1919初始关键字初始关键字:494952656597973535131327274949表表n=8n=8第一趟：第一趟：d1=n/2=435354949第二趟：第二趟：d2=d1/2=22727353549496565第三趟：第三趟：d3=d2/2=11313273535494949495252656597973535134949525235351327274949525265653535
8、13272749494949525265659797272713353549494949525265659797希尔排序排序过程希尔排序排序过程【例】2020 Shell排序排序定义一个递增序列定义一个递增序列：d1 d2 dt(d1=1)分步骤进行分步骤进行“间隔间隔dk-插入排序插入排序”，k=t,t 1,1,即即:将记录序列将记录序列按增量按增量dk分成若干子序列，每个子序列分别进行每个子序列分别进行“跳跃式跳跃式”插入排序插入排序。直到直到增量为增量为1，所有记录为一组所有记录为一组，得到有序序列得到有序序列。“间隔“间隔dk-插入排序”插入排序”的结果留给“间隔的结果留给“间隔dk-
9、1-插入插入排序”排序”希尔排序特点：21211.void ShellInsert(SqList&L,int dk)2.for(i=dk+1;i=L.length;+i)3.if(L.ri.key0&(L.r0.keyL.rj.key);j-=dk)6.L.rj+dk=L.rj;/记录后移，查找插入位置记录后移，查找插入位置7.L.rj+dk=L.r0;/插入插入8.9.希尔排序算法2222void ShellSort(SqList&L,int dlta,int t)/增量为增量为dlta的希尔排序的希尔排序for(k=1;kt;+k)ShellInsert(L,dltak);/一趟增量为一趟
10、增量为dltak的插入排序的插入排序 希尔排序算法（续）2323希尔排序算法的整体时间复杂度和增量序列的选取有关，目前并没有统一的最优增量序列。当使用增量序列 N/2 ,N/22 ,1 进行希尔排序时，有例子表明，最差情况下的时间复杂度Tworst(n)=O(N2)；而当使用增量序列 2k-1,7,3,1 时，最差情况下时间复杂度为Tworst(n)=O(N3/2)，平均时间复杂度为Taverage(n)=O(N5/4)。希尔排序算法分析2424(1)稳定性希尔排序是不稳定的排序方法。(2)算法效率a.时间复杂度 T(n)最坏：O(n2)平均：O(n1.3)到平均O(n1.5)b.空间复杂度 S(n)：O(1)。希尔排序算法分析（续）25The end