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

新东方在线 > 考研 > 计算机 > 考研计算机资料 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2022计算机考研知识点梳理：排序的定义

2021-04-21 07:27:00来源：网络

　　 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考研 计算机资料

考研英语核心词汇营

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

更多资料

添加班主任领资料

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

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

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

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

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

测评合集

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

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