首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机复习指导 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2020考研计算机《数据结构(C语言版)》复习笔记(8)

2019-05-24 08:46:41来源：网络

　　2020年计算机考研复习已经开始，新东方在线在此整理了2020考研计算机《数据结构(C语言版)》复习笔记(8)，希望能帮助大家!

　　第八章 排序知识点整理

　　记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。

　　排序是使文件中的记录按关键字递增(或递减)次序排列起来。

　　·基本操作：比较关键字大小;改变指向记录的指针或移动记录。

　　·存储结构：顺序结构、链表结构、索引结构。

　　经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。

　　排序过程中不涉及数据的内、外存交换则称之为“内部排序”(内排序)，反之，若存在数据的内外存交换，则称之为外排序。

　　内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。

　　评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。

　　插入排序：·直接插入排序： ·逐个向前插入到合适位置。

　　·哨兵(监视哨)有两个作用： ·作为临变量存放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)的排序方法;

　　·记录的大小(规模)：记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现;

　　·关键字的结构及其初始状态：　　·对稳定性的要求;

　　·语言工具的条件： 　　·存储结构;　　·时间和辅助空间复杂度。


本文关键字: 2020考研计算机

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

名师试听

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10