培训啦 学历 考研

2021计算机专业考研数据结构知识点:排序

发布时间: 2022-12-27 04:03:17
2021计算机专业考研数据结构知识点:排序

2021计算机专业考研数据结构知识点:排序

对于大多数2021考生来说考研还是最初的准备阶段,基本上还没有进入复习节奏,而对于计算机专业课的复习,相对来说还更早一些。为了以后复习不那么吃力,现在可以先了解一下。下面小编整理的“2021计算机专业考研数据结构知识点:排序”相关文章,希望对大家有所帮助。

2021计算机专业考研数据结构知识点:排序

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

以上就是小编整理的“2021计算机专业考研数据结构知识点:排序”相关内容,希望对大家有所帮助,预祝大家能考上理想的院校。



.xqy_container .xqy_core .xqy_core_main .xqy_core_text{height:auto !important;} 2021计算机专业考研数据结构知识点:排序
温馨提示:
本文【2021计算机专业考研数据结构知识点:排序】由作者教培参考提供。该文观点仅代表作者本人,培训啦系信息发布平台,仅提供信息存储空间服务,若存在侵权问题,请及时联系管理员或作者进行删除。
我们采用的作品包括内容和图片部分来源于网络用户投稿,我们不确定投稿用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的权利,请联系我站将及时删除。
内容侵权、违法和不良信息举报
Copyright @ 2024 培训啦 All Rights Reserved 版权所有. 湘ICP备2022011548号