首页 26考研 在职考研 5月备考资料 27考研

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

扫码加入训练营

牢记核心词

学习得礼盒

2021计算机专业考研数据结构知识点：排序

2020-07-22 15:15:00来源：​网络

　　 2021计算机专业考研数据结构知识点：排序

　　对于大多数2021考生来说考研还是最初的准备阶段，基本上还没有进入复习节奏，而对于计算机专业课的复习，相对来说还更早一些。为了以后复习不那么吃力，现在可以先了解一下。下面小编整理的“2021计算机专业考研数据结构知识点：排序”相关文章，希望对大家有所帮助。

　　2021计算机专业考研数据结构知识点：排序

　　1.插入类排序的基本思想是假定待排序文件第一个记录有序，然后从第二个记录起，依次插入到排好序的有序子文件中，直到整个文件有序。从减少比较次数和移动次数进行了各种改进，在插入排序中有直接插入、折半插入、希尔排序。直接插入是依次寻找，折半插入是折半寻找，希尔排序是经过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。

　　2.交换类排序基于相邻记录比较，若逆序则进行交换。起泡排序和快速排序是交换排序的例子，在起换排序的基础上改进得到快速排序，快速排序是目前好的内部排序法。快速排序的思想：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。

　　3.选择类排序，可以分为：简单选择排序、堆排序。这两种方法的不同点是，根据什么规则选取最小的数。简单选择，是经过简单的数组遍历方案确定最小数堆排序,是利用堆这种数据结构的性质，经过堆元素的删除、调整等一系列操作将最小数选出放在堆顶堆排序较为重要，其最差性能比快速排序的最差性能好。

　　4.归并排序是经过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并，算法思想比较简单。

　　5.基数排序，是一种特殊的排序方法，分为两种：多关键字的排序(扑克牌排序)，链式排序(整数排序)。基数排序的重要思想也是利用“基数空间”这个概念将问题规模规范、变小，在排序的过程中，只要按照基数排序的思想，是不用进行关键字比较的,这样得出的最终序列就是一个有序序列。

　　6.掌握各种排序方法的算法思想以及算法实现。掌握在好、最坏、平均情况下各种排序方法的性能分析。归并排序、基数排序及时间复杂度为 O(n2)的排序是稳定排序，而希尔排序、快速排序、堆排序等时间性能好的排序方法是不稳定排序(但特别注意，简单选择排序是不稳定排序)。 各种排序方法的综合比较。

　　(1)时间性能

　　按平均的时间性能来分，有三类排序方法：

　　时间复杂度为 O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为好

　　时间复杂度为 O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为好，特别是对那些对关键字近似有序的记录序列尤为如此

　　时间复杂度为 O(n)的排序方法只有，基数排序。

　　当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到 O(n)的时间复杂度而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为 O(n2)，因此是应该 尽量避免的情况。

　　简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

　　(2)空间性能：指的是排序过程中所需的辅助空间大小。

　　所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)

　　快速排序为 O(logn)，为栈所需的辅助空间

　　归并排序所需辅助空间多，其空间复杂度为 O(n)

　　链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。

　　(3)排序方法的稳定性能

　　稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。

　　当对多关键字的记录序列进行 LSD方法排序时，必须采用稳定的排序方法。 对于不稳定的排序方法，只要能举出一个实例说明即可。 快速排序和堆排序是不稳定的排序方法。

　　以上就是小编整理的“2021计算机专业考研数据结构知识点：排序”相关内容，希望对大家有所帮助，预祝大家能考上理想的院校。

　　


本文关键字: 2021 计算机考研 数据结构 排序

声明：如本网转载稿涉及版权等问题，请作者致信lulei@xdfzx.com，我们将及时处理。

限时免费
资料推荐

添加班主任领资料

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

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

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

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

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

考研资料大礼包

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

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
获取验证码
收不到短信？点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码
获取验证码
收不到短信？点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码
前去听课
获取验证码
收不到短信？点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码