您所在的位置：四川中公考研 > 备考资料 > 考研专硕 > 2020计算机职业考研数据结构知识点：排序

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

发布日期：2019-06-12 20:41:39 来源：四川中公考研

2020考研择校择职业指导群

点击关注“四川中公考研”新浪微博，与博主互动获取考研上名校技巧

点击关注“四川中公考研”微信公众号，第一时间获取新考研资讯

职业课协议班、周末面授班、半年集训、暑期集训营

本文是四川中公考研网小编整理的关于“2020计算机职业考研数据结构知识点：排序"的相关资讯信息，供大家参考。
　 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方法排序时，必须采用稳定的排序方法。对于不稳定的排序方法，只要能举出一个实例说明即可。快速排序和堆排序是不稳定的排序方法。
更多考研常识相关内容尽在四川中公考研专硕栏目，中公考研为广大学子推出乐学面授课、VIP一对一等系列备考课程，针对每一个科目要点进行深入的指导分析，欢迎各位考生了解咨询。同时，中公考研一直为大家推出考研直播课堂，足不出户就可以边听课边学习，为大家的考研梦想助力！

免责声明：本站所提供的内容均来源于网友提供或网络搜集，由本站编辑整理，仅供个人研究、交流学习使用，不涉及商业盈利目的。如涉及版权问题，请联系本站管理员予以更改或删除。

【责任编辑：白红梅】

上一篇： 2020计算机职业考研数据结构知识点：图

下一篇： 2020计算机职业考研数据结构知识点：查找

预约报名流程

考研指导图书

热点推荐

中公考研课堂

公共课
|专业课

课程系列	班次名称	价格	免费试听
考研政治网络课堂	2022考研政治+英语提升课程	咨询	免费试听
考研政治网络课堂	考研政治主观题答题技巧班	咨询	免费试听
考研英语网络课堂	2022考研政英数提升课程	咨询	免费试听
考研英语网络课堂	2022考研英语备考指导课	咨询	免费试听
考研数学网络课堂	2022考研数学备考指导课	咨询	免费试听
	2022考研数学（二）	咨询	免费试听
	2022考研数学（三）	咨询	免费试听
22专业课精品班	2022考研英语核心词汇精讲	咨询	免费试听
	9天突破英语核心1000词	咨询	免费试听
	2022考研管综备考指导课	咨询	免费试听

课程系列	班次名称	价格	免费试听
经济学精品班	2021考研经济学	咨询	免费试听
教育学精品班	经济学（初级）考研入门课	咨询	免费试听
教育学精品班	经济学（中级）考研入门课	咨询	免费试听
法学精品班	法律硕士（非法学）考研入门课	咨询	免费试听
法学精品班	2022考研法律硕士	咨询	免费试听
管理学精品班	管理学考研入门课	咨询	免费试听
管理学精品班	考研管理学全科精讲	咨询	免费试听