数据结构复习要点第八章排序
立即购买
《自考视频课程》名师讲解,轻松易懂,助您轻松上岸!低至199元/科!
记录中可用某一项来标识一个记录,则称为关键字项,该数据项的值称为关键字。
排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作:比较关键字大小;改变指向记录的指针或移动记录。
·存储结构:顺序结构、链表结构、索引结构。
经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的,否则排序算法是不稳定的。
排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序),反之,若存在数据的内外存交换,则称之为外排序。
内部排序方法可分五类:插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条:执行时间和所需的辅助空间,另外算法的复杂程序也是要考虑的一个因素。
插入排序:·直接插入排序: ·逐个向前插入到合适位置。
·哨兵(监视哨)有两个作用: ·作为临变量存放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)的排序方法;
·记录的大小(规模);记录大最好用链表作为存储结构,而快速排序和堆排序在链表上难于实现;
·关键字的结构及其初始状态;
·对稳定性的要求;
·语言工具的条件;
·存储结构;
·时间和辅助空间复杂度
本文标签:河南自考 串讲笔记 数据结构复习要点第八章排序
转载请注明:文章转载自(http://www.hazikao.net)
《河南自考网》免责声明:
1、由于各方面情况的调整与变化,本网提供的考试信息仅供参考,考试信息以省考试院及院校官方发布的信息为准。
2、本网信息来源为其他媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。联系邮箱:812379481@qq.com。
相关《数据结构复习要点第八章排序》的文章