计算机考研:数据结构常用算法精析(9)
2013.12.12 15:18

  

  数据结构是计算机考研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)),不需要辅助空间,但有最好和最差之分

MORE+

    相关阅读 MORE+

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

    Copyright © 2011-202

    All Rights Reserved