2020考研计算机数据结构知识点:排序
2019.04.30 18:58

  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方法排序时,必须采用稳定的排序方法。 对于不稳定的排序方法,只要能举出一个实例说明即可。 快速排序和堆排序是不稳定的排序方法。


MORE+

    相关阅读 MORE+

    版权及免责声明
    1.凡本网注明"稿件来源:新东方在线"的所有文字、图片和音视频稿件,版权均属北京新东方迅程网络科技有限公司所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本网协议授权的媒体、网站,在下载使用时必须注明"稿件来源:新东方在线",违者本网将依法追究责任。
    2.本网末注明"稿件来源:新东方在线"的文/图等稿件均为转载稿,本网转载出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的"稿件来源",并自负版权等法律责任。如擅自篡改为"稿件来源:新东方在线”,本网将依法追究责任。
    3.如本网转载稿涉及版权等问题,请作者致信weisen@xdfzx.com,我们将及时外理

    Copyright © 2011-202

    All Rights Reserved