地市
湖南中公考研

 地址:长沙市芙蓉区建湘路521号轻工盐业大厦9层

 电话:400-6300-966

邵阳中公教育

 地址:邵阳市人民广场五一北路口正太大厦3楼

 电话:0739-5111550

常德中公教育

 地址:常德市滨湖路666号时代广场1、3楼

 电话:0736-7191133

娄底中公教育

 地址:娄底市娄星区乐坪大道锦洋大厦8楼

 电话:0738-8278055/8278056

株洲中公教育

 地址:株洲市中心广场家润多大厦A座12层

 电话:0731-28210432,0731-28105586

永州中公教育

 地址:永州市冷水滩区河西舜德财富中心1901-1908室

 电话:0746-2836699

衡阳中公教育

 地址:衡阳市船山西路益福花园2楼

 电话:0734-8148585/8120929

岳阳中公教育

 地址:岳阳市巴陵中路93号建设银行5楼(军分区旁)

 电话:0730-8226822,18973009240

怀化中公教育

 地址:怀化市迎丰中路238号明辉大酒店2楼

 电话:0745-2856177,0745-2256177

郴州中公教育

 地址:郴州国庆南路29号(七天优品酒店4楼)

 电话:0735-2888085

湘潭中公教育

 地址:湘潭市雨湖区韶山中路112号二楼回家餐厅对门

 电话:0731-58259256

益阳中公教育

 地址:益阳市康富北路2号信义楼3楼(华天壹号公馆旁)

 电话:0737-6111226,6113226

湘西中公教育

 地址:吉首市人民北路77号(吉首关厢门建行旁)

 电话:0743-8551911,0743-8729860

张家界中公教育

 地址:张家界永定区黄金大厦12楼

 电话:0744-8222244

 您所在的位置:湖南中公考研 > 备考资料 > 考研专硕 > 2020计算机专业考研数据结构知识点:排序

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

来源:中公考研 发布日期:2019-06-12 10:57:05

  对于大多数2020考生来说考研还是最初的准备阶段,基本上还没有进入复习节奏,而对于计算机专业课的复习,相对来说还更早一些。为了以后复习不那么吃力,现在可以先了解一下。下面中公考研小编整理的“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方法排序时,必须采用稳定的排序方法。 对于不稳定的排序方法,只要能举出一个实例说明即可。 快速排序和堆排序是不稳定的排序方法。

  以上就是中公考研小编整理的“2020计算机专业考研数据结构知识点:排序”相关内容,希望对大家有所帮助,预祝大家能考上理想的院校。更多计算机考研信息尽在中公考研计算机频道!

2020考研热门推荐
现场确认地点 最后2月,冲刺集训 考前特训营 不过退费 考前预测密卷免费领
在线咨询 招生简章预约 考研题库下载 在职考研群
更多考研资讯请访问湖南考研网

关注微信公众号hnzgkaoyan365,本地考研信息不错过
湖南中公考研微信

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

【责任编辑:向倩】

中公考研课堂

  • 公共课
  • |专业课
课程系列 班次名称 价格 免费试听
考研政治网络课堂 2020考研政治新大纲突击班直播网课 ¥799.00  免费试听
2020考研政治全程协议班 ¥1080.00  免费试听
考研英语网络课堂 2020考研英语一全程班 ¥980.00  免费试听
2020考研英语二全程班 ¥980.00  免费试听
考研数学网络课堂 2020考研数学一全程班 ¥980.00  免费试听
2020考研数学二全程班 ¥980.00  免费试听
2020考研数学三全程班 ¥980.00  免费试听
全程联报课程 2020考研政治+英语一+数学一全程联报协议班 ¥2140.00  免费试听
2020考研政治+英语二+数学三全程联报协议班 ¥2140.00  免费试听
2020考研英语二+数学二全程联报协议班 ¥1560.00  免费试听
课程系列 班次名称 价格 免费试听
经济学考研网络课堂 2020考研经济学精品班(宏观+微观+政经) ¥1580.00  免费试听
2020考研经济学全科精品班 ¥3040.00  免费试听
管理学考研网络课堂 2020考研管理学精品班(周三多) ¥1580.00  免费试听
2020考研管理学全科精品班 ¥3040.00  免费试听
西医考研网络课堂 2020考研西医综合精品班 ¥1880.00  免费试听
2020考研西医综合全科精品班 ¥3040.00  免费试听
教育学考研网络课堂 2020考研教育学精品班 ¥1880.00  免费试听
心理学考研网络课堂 2020考研心理学精品班 ¥1880.00  免费试听
中医考研网络课堂 2020考研中医综合精品班 ¥1880.00  免费试听
2020考研中医综合全科精品班 ¥3040.00  免费试听
计算机考研网络课堂 2020考研计算机精品班 ¥1580.00  免费试听
艺术学考研网络课堂 2020考研中国美术史精讲班 ¥1080.00  免费试听
 2020考研秋季集训营

中公秋季备考路径,让考研变得"更简单",中公秋季训练营,百天高效提升50+,未达协议分数退学费GO>

 2021考研起跑计划

2021考研起跑计划,干货分享,助你备考有方,事半功倍,稳步上岸GO>


  •  

报考信息

备考指导

湖南中公考研

 长沙市芙蓉区建湘路521号轻工盐业大厦8层中公教育

 网址:hn.kaoyan365.cn

 电话:400-6300-966

咨询时间

周一至周日 9:00-18:00 全年无休在线客服

湖南中公考研互动平台 

湖南中公考研微信

湖南中公考研微信

湖南中公考研微博

湖南中公考研微博

  • 长沙
  • 邵阳
  • 常德
  • 娄底
  • 株洲
  • 永州
  • 衡阳
  • 岳阳
  • 怀化
  • 郴州
  • 湘潭
  • 益阳
  • 湘西
  • 张家界
  • 湖南中公教育

    地址:长沙市芙蓉区五一大道800号中隆国际大厦4-5层

    电话:0731-84883717,4006-300-999

  • 湖南中公考研

    地址:长沙市芙蓉区建湘路521号轻工盐业大厦8层

    电话:400-6300-966

  • 星沙中公教育

    地址:长沙县开元中路88号星隆国际广场12A楼

    电话:0731-84011175,17773157075

  • 浏阳中公教育

    地址:长沙浏阳市金沙北路499号(集里路口公交站)

    电话:0731-89636075,17788956075

  • 中公农大学习中心

    地址:湖南农业大学红旗市场旁[库堡]1号门面

    电话:0731-84067637

  • 中公涉外学习中心

    地址:长沙市岳麓区涉外西门天元七彩B区商业3037

    电话:186-2759-8841

  • 中公长理学习中心

    地址:长沙理工大学云塘校区西门梦圆城2楼(美食城楼下)

    电话:189-7498-5792

  • 中公林科大学习中心

    地址:长沙市林科大东门步步高超市三楼(绝味鸭脖旁楼上)

    电话:156-7516-1435

  • 中公财院学习中心

    地址:湖南财政经济学院东门金枫酒店4楼(地铁金星路2A口)

    电话:181-8653-3166

  • 中公宁乡学习中心

    地址:长沙宁乡市花明北路中源凝香华都3栋(人人乐附近)

    电话:0731-87978936

  • 邵阳中公教育

    地址:邵阳市人民广场五一北路口正太大厦3楼

    电话:0739-5111550,0739-5111552

  • 中公洞口县学习中心

    地址:洞口县商业步行街内50米

    电话:0739-7151550

  • 中公邵东县学习中心

    地址:邵东县昭阳大道与金龙大道交叉口

    电话:0739-2722550

  • 中公武冈市学习中心

    地址:邵阳武冈市陶侃路9号(交警大队往东走200米)

    电话:0739-4222550

  • 常德中公教育

    地址:常德市滨湖路666号时代广场1、3楼

    电话:0736-7191133,0736-7168660

  • 中公澧县学习中心

    地址:常德市澧县桃花滩路锦绣玫瑰园23栋1单元

    电话:0736-3217058

  • 中公汉寿学习中心

    地址:汉寿县龙阳中路617号综合楼三楼

    电话:0736-2098660

  • 中公桃源学习中心

    地址:桃源县漳江镇渔父北路文昌阁居委会对面二楼

    电话:0736-6681663

  • 中公石门学习中心

    地址:石门县宝塔社区电厂路18号

    电话:0736-5012729

  • 中公湖南文理学院学习中心

    地址:常德市武陵区滨湖路1400号

    电话:186-7001-1014

  • 娄底中公教育

    地址:娄底市娄星区乐坪大道锦洋大厦8楼

    电话:0738-8278055/8278056

  • 中公人文学习中心

    地址:娄底市湖南人文科技学院正门对面

    电话:0738-8278050

  • 中公新化学习中心

    地址:新化县县政府正门斜对面(祥和街往里走20米)

    电话:0738-3211980

  • 株洲中公教育

    地址:株洲市中心广场家润多大厦A座12层

    电话:0731-28210432,0731-28105586

  • 中公攸县学习中心

    地址:株洲攸县滨江大道望云新外滩2期99号-101号

    电话:13873340113 17397330113

  • 中公工大学习中心

    地址:湖南工业大学河西校区北苑一食堂工大美食广场二楼

    电话:189-7418-5563

  • 永州中公教育

    地址:永州市冷水滩区河西舜德财富中心1901-1908室

    电话:0746-2836699

  • 中公江华学习中心

    地址:江华县政府小街1号楼3层(县政府旁

    电话:0746-2334566

  • 中公宁远学习中心

    地址:宁远县九疑南路268号(县人社局斜对面)

    电话:0746-7662066

  • 中公东安学习中心

    地址:东安县东安大道93号(县移动总公司旁)县政府对面

    电话:0746-4235066

  • 中公蓝山学习中心

    地址:蓝山县湘粤路180号(县劳动局旁)

    电话:0746-2225366

  • 中公新田学习中心

    地址:新田县云鹤路思源实验学校正对面三楼

    电话:0746-4767599

  • 湖南科技学院学习中心

    地址:湖南科技学院创新创业学院三楼

    电话:180-0746-0311

  • 中公道县学习中心

    地址:道县道江镇道州南路113号(党校正对面)

    电话:199-6762-2293

  • 中公祁阳学习中心

    地址:祁阳县浯溪镇复兴路

    电话:152-1132-4650

  • 衡阳中公教育

    地址:衡阳市船山西路益福花园2楼

    电话:0734-8148585/8120929

  • 衡东学习中心

    地址:湖南衡东县洣江大道恒瑞酒店公交车站旁

    电话:0734-5232838

  • 岳阳中公教育

    地址:岳阳市巴陵中路93号建设银行5楼(军分区旁)

    电话:0730-8226822,18973009240

  • 怀化中公教育

    地址:怀化市迎丰中路238号明辉大酒店2楼

    电话:0745-2856177,0745-2256177

  • 溆浦学习中心

    地址:湖南省怀化市溆浦县城南幸福路8号

    电话:0745-3337677

  • 通道学习中心

    地址:通道县杉山街(气象局对面)

    电话:0745-8621527,13349654357

  • 中公麻阳学习中心

    地址:麻阳县锦江财富中心8楼B88

    电话:0745-5830277 18166215375

  • 郴州中公教育

    地址:郴州国庆南路29号(七天优品酒店4楼)

    电话:0735-2888085

  • 中公郴州安仁学习中心

    地址:安仁县七一西路立邦花园14号1楼门面

    电话:0735-5440070

  • 中公郴州桂阳学习中心

    地址:桂阳县士杰路竹苑新城一楼104号门面

    电话:0735-4423380

  • 湘潭中公教育

    地址:湘潭市雨湖区韶山中路112号二楼回家餐厅对门

    电话:0731-58259256

  • 中公湘大学习中心

    地址:湘潭大学北苑太平市场6-7号

    电话:0731-55582999

  • 中公湖科大学习中心

    地址:湖南科技大学南堕落街维拉斯健身一楼中公教育

    电话:0731-58238899

  • 益阳中公教育

    地址:益阳市康富北路2号信义楼3楼(华天壹号公馆旁)

    电话:0737-6111226

  • 湘西中公教育

    地址:吉首市人民北路77号(吉首关厢门建行旁)

    电话:0743-8551911,0743-8729860

  • 中公花垣县学习中心

    地址:花垣县城北双龙潭大桥旁三楼

    电话:0737-6111226

  • 中公永顺县学习中心

    地址:永顺县灵溪镇大桥街419号中公教育

    电话:0743-5230950

  • 中公吉首吉大学习中心

    地址:吉首大学(沙子坳校区)网球场正对面二楼

    电话:0743-8729006

  • 张家界中公教育

    地址:张家界永定区黄金大厦12楼

    电话:0744-8222244