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

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

扫码加入训练营

牢记核心词

学习得礼盒

计算机考研：数据结构常用算法精析(9)

2013-12-12 15:18:39来源：新东方在线编辑

　　

　　数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握。新东方在线小编下面一一为大家分析一下，帮助考生更好地去掌握。

　　第十章

　　内部排序(在内存中进行的排序不需要访问外存的)外部排序(排序量很大，通过分批的读写外存，最终完成排序)

　　稳定排序和非稳定排序：看相同记录的相对次序是否回发生改变。主要看在排序过程中的比较是不是相邻记录，如果是相邻比较，一定是稳定的排序。如果不是相邻的比较，就是不稳定的。

　　内排序方法 截止目前，各种内排序方法可归纳为以下五类：

　　(1)插入排序;(2)交换排序;(3)选择排序;(4)归并排序; (5)基数排序。

　　插入排序：包括直接插入排序和希尔排序

　　直接插入排序：(稳定的)

　　算法描述

　　void Insort (sqList &L) ∥对顺序文件F直接插入排序的算法∥

　　{ int i,j;

　　for (i=2;i<=L.len;i++) ∥插入n-1个记录∥

　　{

　　if(L.R[i].key

　　{ L.R[0]=L.R[i]; ∥待插入记录先存于监视哨∥

　　L.R[i]=L.R[i-1];

　　for(j=i-2;L.R[0].key

　　L.R[j+1]=L.R[j]; ∥记录顺序后移∥

　　L.R[j+1]=L.R[0]; ∥原R[i]插入j+1位置∥

　　}

　　}

　　}

　　算法分析

　　设排序中key比较次数为C，C最小时记为Cmin，最大时记为Cmax。

　　(1)当原来就有序(正序)时，每插入一个R[i]只需比较key一次，即：

　　(2)当原本逆序(key从大到小)时，每插入一个R[i]要和子表中i-1个key比较，加上同自身R[0]的比较，此时比较次数最多，即：

　　(3)记录总的移动次数m(m最小时记为mmin，最大时记为mmax)

　　正序时，子表中记录的移动免去，即：

　　逆序时，插入R[i]牵涉移动整个子表。移动次数为2+(i-1)=i+1，此时表的移动次数最大，即：

　　排序的时间复杂度取耗时最高的量级，故直接插入排序的T(n)=O(n2)。

　　Shell(希尔)排序又称“缩小增量”排序(不稳定的)

　　交换类的排序：(起泡排序和快速排序)

　　起泡排序算法描述

　　void Bubsort (sqList &L)

　　{ int i,flag; ∥flag为记录交换的标记∥

　　Retype temp;

　　for (i=L.len;i>=2;i--) ∥最多n-1趟排序∥

　　{ flag=0; //记录每一趟是否发生了交换

　　for (j=1;j<=i-1;j++) ∥一趟的起泡排序∥

　　if (L.R[j].key>L.R[j+1].key) ∥两两比较∥

　　{ temp=L.R[j]; ∥R[j] Û R[j+1]∥

　　L.R[j]=L.R[j+1];

　　L.R[j+1]=temp;

　　flag=1;

　　}

　　if (flag==0) break; ∥无记录交换时排序完毕∥

　　}

　　}

　　算法分析

　　设待排长度为n，算法中总的key比较次数为C。若正序，第一趟就无记录交换，退出循环，Cmin=n-1=O(n);若逆序，则需n-1趟排序，每趟key的比较次数为i-1(2≤i≤n)，故：

　　同理，记录的最大移动次数为：

　　故起泡排序的时间复杂度T(n)=O(n2)。并且是稳定的。

　　快速排序：(不稳定的，时间复杂度O(nlogn))，不需要辅助空间，但有最好和最差之分

考研公开课小程序

本文关键字: 计算机 考研 数据结构

上一页 1 2 3 下一页

考研英语核心词汇营

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

更多资料

添加班主任领资料

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

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

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

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

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

名师试听

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

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