咨询电话:400-6300-966
资讯中心
搜索

2022年计算机考研知识点:排序的定义

来源:中公考研网校 更新时间:2021年03月25日 16:24:06

计算机专业如今竞争日趋激烈,考题形式多样涵盖的内容较多,对于报考计算机专业同学来说复习是难点,2022考研计算机的考生们要提早开始着手准备了。中公考研网校为大家提供了“2022计算机考研知识点梳理:排序的定义”,赶快学习来吧。

2022年计算机考研知识点:排序的定义

排序,就是重新排列表中的元素,使表中的元素满足按关键字有序的过程。为了查找方便,通常希望计算机中的表是按关键字有序的。排序的确切定义如下:

  输入:n个记录R₁,R₂,…,R n,对应的关键字为k₁,k₂,…,kn。

  输出:输入序列的一个重排 R₁',R₂',…,Rn',使得k₁'≤k₂'≤ …≤k n'(其中“≤”可以换成其他的比较大小的符号)。

  算法的稳定性。若待排序表中有两个元素R i,和R j,其对应的关键字相同即key i=key j,且在排序前Ri在Rj的前面,若使用某一排序算法排序后,Ri仍然在Rj的前面,则称这个排序算法是稳定的,否则称排序算法是不稳定的。需要注意的是,算法是否具有稳定性并不能衡量一个算法的优劣,它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复,则排序结果是仅有的,那么选择排序算法时的稳定与否就无关紧要。

  注意:对于不稳定的排序算法,只需举出一组关键字的实例,说明它的不稳定性即可。

  在排序过程中,根据数据元素是否完全在内存中,可将排序算法分为两类:①内部排序,是指在排序期间元素全部存放在内存中的排序:②外部排序,是指在排序期间元素无法全部同时存放在内存中,必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

  一般情况下,内部排序算法在执行过程中都要进行两种操作:比较和移动。通过比较两个关键字的大小,确定对应元素的前后关系,然后通过移动元素以达到有序。当然,并非所有的内部排序算法都要基于比较操作,事实上,基数排序就不基于比较。

  每种排序算法都有各自的优缺点,适合在不同的环境下使用,就其性能而言,很难提出一种被认为是较好的算法。通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类。内部排序算法的性能取决于算法的时间复杂度和空间复杂度,而时间复杂度一般是由比较和移动的次数决定的。

以上就是中公考研网校为大家整理的“2022年考研计算机组成原理复习知识点 :排序的定义”相关内容,掌握基础知识目的是让广大学员都能够打下一个坚实的基础,为以后的深入学习做好充分的准备。

相关推荐

2022考研计算机全程进阶班

2022考研计算机定向全科直通车

全国考研难度排行榜--前100名

2022考研“在职人”英语一专属班

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

【责任编辑:mhf80817 】

共1页 当前第1页
免费资料
历年试题
考试大纲
备考计划
0元好课
思维导图
核心考点
手机号快捷登录
账号密码登录
本周热门直播

更多直播