• 关于

    判定边界不可用

    的搜索结果

回答

本人学习数据结构时看到的不错的总结,共享一下了 文件有一组记录组成,记录有若干数据项组成,唯一标识记录的数据项称关键字; 排序是将文件按关键字的递增(减)顺序排列; 排序文件中有相同的关键字时,若排序后相对次序保持不变的称稳定排序,否则称不稳定排序; 在排序过程中,文件放在内存中处理不涉及数据的内、外存交换的称内部排序,反之称外部排序; 排序算法的基本操作:1)比较关键字的大小;2)改变指向记录的指针或移动记录本身。 评价排序方法的标准:1)执行时间;2)所需辅助空间,辅助空间为O(1)称就地排序;另要注意算法的复杂程度。 若关键字类型没有比较运算符,可事先定义宏或函数表示比较运算。 8.2插入排序 8.2.1直接插入排序 实现过程: void insertsort(seqlist R) { int i, j; for(i=2;i<=n;i++) if(R[i].key< R[i-1].key{ R[0]=R[i];j=i-1; do{R[j+1]=R[j];j--;} while(R[0].key R[j+1]=R[0]; } } 复制代码 算法中引入监视哨R[0]的作用是:1)保存 R[i] 复制代码 的副本;2)简化边界条件,防止循环下标越界。 关键字比较次数最大为(n+2)(n-1)/2;记录移动次数最大为(n+4)(n-1)/2; 算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序; 8.2.2希尔排序 实现过程:是将直接插入排序的间隔变为d。d的取值要注意:1)最后一次必为1;2)避免d值互为倍数; 关键字比较次数最大为n^1.25;记录移动次数最大为1.6n^1.25; 算法的平均时间是O(n^1.25);是一种就地的不稳定的排序; 8.3交换排序 8.3.1冒泡排序 实现过程:从下到上相邻两个比较,按小在上原则扫描一次,确定最小值,重复n-1次。 关键字比较次数最小为n-1、最大为n(n-1)/2;记录移动次数最小为0,最大为3n(n-1)/2; 算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序; 8.3.2快速排序 实现过程:将第一个值作为基准,设置i,j指针交替从两头与基准比较,有交换后,交换j,i。i=j时确定基准,并以其为界限将序列分为两段。重复以上步骤。 关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2; 算法的最好时间是O(nlog2n);最坏时间是O(n^2);平均时间是O(nlog2n);辅助空间为O(log2n);是一种不稳定排序; 8.4选择排序 8.4.1直接选择排序 实现过程:选择序列中最小的插入第一位,在剩余的序列中重复上一步,共重复n-1次。 关键字比较次数为n(n-1)/2;记录移动次数最小为0,最大为3(n-1); 算法的最好时间是O(n^2);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的不稳定的排序; 8.4.2堆排序 实现过程:把序列按层次填入完全二叉树,调整位置使双亲大于或小于孩子,建立初始大根或小根堆,调整树根与最后一个叶子的位置,排除该叶子重新调整位置。 算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);是一种就地的不稳定排序; 8.5归并排序 实现过程:将初始序列分为2个一组,最后单数轮空,对每一组排序后作为一个单元,对2个单元排序,直到结束。 算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);辅助空间为O(n);是一种稳定排序; 8.6分配排序 8.6.1箱排序 实现过程:按关键字的取值范围确定箱子的个数,将序列按关键字放入箱中,输出非空箱的关键字。 在桶内分配和收集,及对各桶进行插入排序的时间为O(n),算法的期望时间是O(n),最坏时间是O(n^2)。 8.6.2基数排序 实现过程:按基数设置箱子,对关键字从低位到高位依次进行箱排序。 算法的最好时间是O(d*n+d*rd);最坏时间是O(d*n+d*rd);平均时间是O(d*n+d*rd);辅助空间O(n+rd);是一种稳定排序; 8.7各种内部排序方法的比较和选择 按平均时间复杂度分为: 1) 平方阶排序:直接插入、直接选择、冒泡排序; 2) 线性对数阶:快速排序、堆排序、归并排序; 3) 指数阶:希尔排序; 4) 线性阶:箱排序、基数排序。 选择合适排序方法的因素:1)待排序的记录数;2)记录的大小;3)关键字的结构和初始状态;4)对稳定性的要求;5)语言工具的条件;6)存储结构;7)时间和辅助空间复杂度。 结论: 1) 若规模较小可采用直接插入或直接选择排序; 2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序; 3) 若规模较大可采用快速排序、堆排序或归并排序; 4) 任何借助于比较的排序,至少需要O(nlog2n)的时间,箱排序和基数排序只适用于有明显结构特征的关键字; 5) 有的语言没有提供指针及递归,使归并、快速、基数排序算法复杂; 6) 记录规模较大时为避免大量移动记录可用链表作为存储结构,如插入、归并、基数排序,但快速、堆排序在链表上难以实现,可提取关键字建立索引表,然后对索引表排序。 附二: 第八章排序 ************************************************************************************* 记录中可用某一项来标识一个记录,则称为关键字项,该数据项的值称为关键字。 排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作:比较关键字大小;改变指向记录的指针或移动记录。 ·存储结构:顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的,否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序),反之,若存在数据的内外存交换,则称之为外排序。 内部排序方法可分五类:插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的标准主要有两条:执行时间和所需的辅助空间,另外算法的复杂程序也是要考虑的一个因素。 ************************************************************************************* 插入排序:·直接插入排序: ·逐个向前插入到合适位置。 ·哨兵(监视哨)有两个作用: ·作为临变量存放 R[i] 复制代码 ·是在查找循环中用来监视下标变量j是否越界。 ·直接插入排序是就地的稳定排序。时间复杂度为O(n^2),比较次数为(n+2)(n-1)/2;移动次数为(n+4)(n-1)/2; ·希尔排序: ·等间隔的数据比较并按要求顺序排列,最后间隔为1。 ·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25),比较次数为(n^1.25);移动次数为(1.6n^1.25); 交换排序:·冒泡排序:·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个,后自上向下确定最重的一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O(n^2),比较次数为n(n-1)/2;移动次数为3n(n-1)/2; ·快速排序:·以第一个元素为参考基准,设定、动两个指针,发生交换后指针交换位置,直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n),比较次数为n(n-1)/2; 选择排序:·直接选择排序: ·选择最小的放在比较区前。 ·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2; ·堆排序 ·建堆:按层次将数据填入完全二叉树,从int(n/2)处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆,直到全断开。 ·堆排序是就地不稳定的排序,时间复杂度为O(nlog2n),不适宜于记录数较少的文件。。 归并排序: ·先两个一组排序,形成(n+1)/2组,再将两组并一组,直到剩下一组为止。 ·归并排序是非就地稳定排序,时间复杂度是O(nlog2n), 分配排序:·箱排序: ·按关键字的取值范围确定箱子数,按关键字投入箱子,链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O(n). ·基数排序:·从低位到高位依次对关键字进行箱排序。 ·基数排序是非就稳定的排序,时间复杂度是O(d*n+d*rd)。 各种排序方法的比较和选择: ·.待排序的记录数目n;n较大的要用时间复杂度为O(nlog2n)的排序方法; ·记录的大小(规模);记录大最好用链表作为存储结构,而快速排序和堆排序在链表上难于实现; ·关键字的结构及其初始状态; ·对稳定性的要求; ·语言工具的条件; ·存储结构; ·时间和辅助空间复杂度。 排序(sort)或分类 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: 输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。 输出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。 1.被排序对象--文件 被排序的对象--文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录,称为关键字项。该数据项的值称为关键字(Key)。 注意: 在不易产生混淆时,将关键字项简称为关键字。 2.排序运算的依据--关键字 用来作排序运算依据的关键字,可以是数字类型,也可以是字符类型。 关键字的选取应根据问题的要求而定。 【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录,则必须用"准考证号"作为关键字。若要按照考生的总分数排名次,则需用"总分数"作为关键字。 排序的稳定性 当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。 在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。 注意: 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。 排序方法的分类 1.按是否涉及数据的内、外存交换分 在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。 注意: ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。 2.按策略划分内部排序方法 可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。 排序算法分析 1.排序算法的基本操作 大多数排序算法都有两个基本的操作: (1) 比较两个关键字的大小; (2) 改变指向记录的指针或移动记录本身。 注意: 第(2)种基本操作的实现依赖于待排序记录的存储方式。 2.待排文件的常用存储方式 (1) 以顺序表(或直接用向量)作为存储结构 排序过程:对记录本身进行物理重排(即通过关键字之间的比较判定,将记录移到合适的位置) (2) 以链表作为存储结构 排序过程:无须移动记录,仅需修改指针。通常将这类排序称为链表(或链式)排序; (3) 用顺序的方式存储待排序的记录,但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表) 排序过程:只需对辅助表的表目进行物理重排(即只移动辅助表的表目,而不移动记录本身)。适用于难于在链表上实现,仍需避免排序过程中移动记录的排序方法。 3.排序算法性能评价 (1) 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条: ① 执行时间和所需的辅助空间 ② 算法本身的复杂程度 (2) 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-PlaceSou)。 非就地排序一般要求的辅助空间为O(n)。 (3) 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态。

马铭芳 2019-12-02 01:19:07 0 浏览量 回答数 0
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 企业信息查询 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站