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

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

扫码加入训练营

牢记核心词

学习得礼盒

2022考研计算机数据结构：各类排序算法的特点及比较

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

　　　 2022考研计算机数据结构：各类排序算法的特点及比较

　　数据结构也是计算机考研常考的科目，部分院校会考试到这一专业课，本文新东方在线计算机考研小编整理分享“计算机数据结构：各类排序算法的特点及比较”相关内容，一起来看看吧。

　　几种主要的排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、Shell排序、堆排序等。

　　冒泡排序算法思想：将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。

　　选择排序算法思想：选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。

　　插入排序算法思想：经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。

　　快速排序算法思想：快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：1. 分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。2. 递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。3. 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。

　　归并排序算法思想：分而治之(divide - conquer)。每个递归过程涉及三个步骤：1.分解，把待排序的n个元素的序列分解成两个子序列，每个子序列包括 n/2 个元素。2. 治理，对每个子序列分别调用归并排序MergeSort，进行递归操作。3. 合并，合并两个排好序的子序列,生成排序结果。

　　Shell排序算法思想：算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

　　堆排序算法思想：用大根堆排序的基本思想：1.先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区。2.再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys&leR[n].key。3. 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。

　　以上是小编为大家整理分享的“计算机数据结构：各类排序算法的特点及比较”相关内容，希望对大家有帮助。祝大家考上理想的院校!更多计算机专业备考信息，敬请关注新东方在线计算机考研网!


本文关键字: 2022考研 计算机复习

考研英语核心词汇营

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

更多资料

添加班主任领资料

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

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

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

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

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

名师试听

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

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