计算机专业课程设计报告

数据结构》课程设计报告姓名： 学号： 5 专业： 网络工程 院系： 计算机科学与技术学院 班级： 指导教师： 2011年6月15日摘要：排序的基本概念(1)排序：将无序的数据序列排列成与关键字有关的数据序列。2各种排序方法•希尔排序：先取第一个增量，把距离为第一个增量的倍数的记录放在同一组中，组内进行直接插入排序：再取小于第一增量的第二增量，重复上述的操作。•快速排序：将原问题分解为若干个小规模的同结构子问题，递归解决每个子问题。•堆排序：先把序列看成一棵大根堆或小根堆，摘取最大或最小元素后再建成新的根堆，再排序。•二路归并排序：将两个有序的子文件合并成一个有序文件，再扩大子文件长度，再次执行上述操作。3．各排序法的比较•元素较大：快速排序、堆排序、归并排序。•元素基本有序：直接插入排序、快速排序。•有益于链表：归并排序。•不利于链表：快速排序、堆排序。•就时间性能而言，快速排序最佳。关键词：排序的概念，各种排序方法，各排序法的比较英文摘要Abstract:1.Sortofbasicconceptssorting:willdisorderdatasequencearrangedandkeywordrelateddata

ernalsort:documentsinmemoryprocessing,sortingdoesnotinvolve,exchangewithinCRT.theexternalsort:sortingprocesstosaveexchangeinsideandoutside.sortingstability:ifthefiletosort,therehaveDuoGekeywordthesamerecord,aftersortwiththesamekeywordsaftertherecordoftherelativeorderbetweenremainunchanged,itsaysthesortingmethodisstable;Conversely,ifhavethesamekeywordrecordsoftherelativeorderbetweenchange,itsaysthesortingmethodisnotstable.2allkindsofsortingmethodHill:thefirsttotakethefirstorderthedistanceforincrementalfirstincrementalmultiplesofrecordsinthesamegroup,thegroupwithinthedirectinsertionsort:takeagainthenextincrementoflessthanfirstincrement,andrepeattheoperation.quicksort:willtheproblemintoseveralsmallsonwithstructure,arecursivesolveeveryproblemson.heapsort:firsttheseriesasatreerootpileoflargeorsmallrootpile,andgatheramaximumorminimumelementbuiltagainafternewrootpileof,againinorder.3.Therankingcomparisonelementbigger:quicksort,目录TOC\o"1-5"\h\z1摘要, 1\o"CurrentDocument"2问题描述 33需求分析 34概要设计 35■数据结构设计 ・361算法设计 46.1.1快速排序 …I612一路归并排序 >56.1.3堆排序 巧6.1.4希尔排序 …6.2算法实现 67.1程序测试与实验 107.1.1主程序- 107.1.2测试数据 117.1.3测试结果 118■性能比较 129心得体会- 13一、问题描述1．题目内容：要求分别采用快速排序、二路归并排序、堆排序和希尔排序对随机生成的一组数据进行排序（数据不少于100）；2．完成排序的输入、输出，比较各种排序的性能，界面友好，提供操作菜单。二、需求分析分别采用快速排序、二路归并排序、堆排序和希尔排序对随机生成的一组数据进行排序（数据不少于100）；将随机产生的数据放在数组data[100]中：操作集合：intPartition(intr[],intfirst,intend)//快速排序，实现一次划分voidQuickSort(intr[],intfirst,intend)//在序列first~end中递归地进行快速排序voidShellSort(intr[],intn)//希尔排序voidMerge(intr[],intr1[],ints,intm,intt)//二路归并排序voidMergePass(intr[],intr1[],intn,inth)voidsift(intr[],intk,intm)//堆排序voidheapsort(intr[],intn)四、数据结构设计1．元素类型intdata[]//定义数组五、算法设计1、算法分析1）、快速排序快速排序的基本思想：首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。需解决的关键问题：⑴如何选择轴值？选择轴值的方法：1.使用第一个记录的关键码；选取序列中间记录的关键码；比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；随机选取轴值。⑵如何实现分割（称一次划分）？解决方法：设待划分的序列是r[s]〜r[t],设参数i,j分别指向子序列左、右两端的下标s和t,令r[s]为轴值，（1） j从后向前扫描，直到r[j]vr[i],将r[j]移动到r[i]的位置，使关键码小（同轴值相比）的记录移动到前面去；（2） i从前向后扫描，直到r[i]>r[j],将r[i]移动到r[j]的位置，使关键码大（同轴值比较）的记录移动到后面去；（3）重复上述过程，直到i=j。⑶如何处理分割得到的两个待排序子序列？解决方法：对分割得到的两个子序列递归地执行快速排序。⑷如何判别快速排序的结束？解决方法：若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。2）、二路归并排序基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列， ，直至得到一个长度为n的有序序列为止。需解决的关键问题：⑴如何将两个有序序列合成一个有序序列？voidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}if(i<=m)while(i<=m)//收尾处理r1[k++]=r[i++]; //前一个子序列elsewhile(j<=t)r1[k++]=r[j++]; //后一个子序列}⑵怎样完成一趟归并？设参数i指向待归并序列的第一个记录，归并的步长是2h,在归并过程中，有以下三种情况：若iWn-2h+l,则相邻两个有序表的长度均为h,执行一次归并，完成后i加2h,准备进行下一次归并；若iVn-h+1,则表示仍有两个相邻有序表，一个长度为h,另一个长度小于h,则执行两个有序表的归并,完成后退出一趟归并。若i三n-h+1,则表明只剩下一个有序表，直接将该有序表送到r1的相应位置,完成后退出一趟归并。⑶如何控制二路归并的结束？算法描述：voidMergeSort(intr[],intr1[],intn){h=1;while(h<n){MergePass(r,r1,n,h);h=2*h;MergePass(r1,r,n,h);h=2*h;3）堆排序基本思想：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。⑴如何由一个无序序列建成一个堆（即初始建堆）？算法描述：for（i=n/2;i>=1;i--）sift（r,i,n）;最后一个结点（叶子）的序号是n，则最后一个分支结点即为结点n的双亲，其序号是n/2。⑵如何处理堆顶记录？解决方法：第i次处理堆顶是将堆顶记录r［1］与序列中第n-i+1个记录r［n-i+l］交换。⑶如何调整剩余记录，成为一个新堆（即重建堆）？解决方法：第i次调整剩余记录，此时，剩余记录有n-i个，调整根结点至第n-i个记录。4）希尔排序基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。（1） 应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？解决方法：将相隔某个“增量”的记录组成一个子序列。增量应如何取？希尔最早提出的方法是d1=n/2，di+1=di/2。（2） 子序列内如何进行直接插入排序？解决方法：在插入记录r［i］时，自r［i-d］起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r［只是暂存单元，不是哨兵。当搜索位置VO,表示插入位置已找到。在搜索过程中，记录后移也是跳跃d个位置。在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。2、算法实现#include"stdafx.h"#include<iostream>#include<iomanip>usingnamespacestd;//快速排序intPartition(intr[],intfirst,intend)//实现一次划分{inttemp,i,j;i=first;j=end; //初始化while(i<j){while(i<j&&r[i]<=r[j])j--;//右侧扫描if(i<j){temp=r[i];r[i]=r[j];r[j]=temp;i++;//将较小记录交换到前面}while(i<j&&r[i]<=r[j])i++;//左侧扫描if(i<j){temp=r[j];r[j]=r[i];r[i]=temp;j--;//将较大记录交换到后面}}returni; //i为轴值记录的最终位置}voidQuickSort(intr[],intfirst,intend){//在序列first~end中递归地进行快速排序if(first<end){intpivotpos=Partition(r,first,end);Quicksort(r,first,pivotpos-1);//对前一个子序列进行快速排序QuickSort(r,pivotpos+1,end);//对后一个子序列进行快速排序}//希尔排序voidShellSort(intr[],intn){for(intd=n/2;d>=1;d=d/2){for(inti=d+l;i〈二n;i++) //将r[i]插入到所属的子序列中{intj;r[0]=r[i]; //暂存待插入记录j=i-d; //j指向所属子序列的最后一个记录while(j>0&&r[0]〈r[j]){r[j+d]=r[j]; //记录后移d个位置j=j-d; //比较同一子序列的前一个记录}r[j+d]=r[0];}}}//二路归并排序voidMerge(intr[],intrl[],ints,intm,intt){inti=s,j=m+l,k=s;while(i〈=m&&j〈=t){if(r[i]〈=r[j]) rl[k++]=r[i++];elserl[k++]=r[j++];}if(i〈=m)while(i〈=m) //收尾处理rl[k++]=r[i++]; //前一个子序列elsewhile(j〈=t)rl[k++]=r[j++]; //后一个子序列}voidMergePass(intr[],intrl[],intn,inth){inti=l;while(i〈=n-2*h+l) //情况{Merge(r,rl,i,i+h-l,i+2*h-l);i+=2*h;//情况if(i<n-h+1)Merge(r,r1,i,i+h-1,n);elsefor(intk=i;k<=n;k++)//情况r1[k]=r[k];//情况}voidMergeSort(intr[],intr1[],intn){inth=1;while(h<n){MergePass(r,r1,n,h);h=2*h;MergePass(r1,r,n,h);h=2*h;}}//堆排序voidsift(intr[],intk,intm){inti,j,x;intt;boolfinished;i=k;j=2*i;t=r[k];x=t;finished=false;while((j<=m)&&(!finished)){if((j<m)&&(r[j]>r[j+1]))j=j+1;if(x<=r[j])finished=true;else{r[i]=r[j];i=j;j=2*i;};};r[i]=t;}voidheapsort(intr[],intn){inti,m;intt;m=n/2;for(i=m;i>=1;i--)sift(r,i,n);for(i=n;i>=2;i--){t=r[1];r[1]=r[i];r[i]=t;sift(r,1,i-1);}}intmain(){intdata[101],data1[101],data2[100],c;cout〈〈"随机产生个随机数为"〈〈endl;for(inti=1;i<=100;i++)data[i]=10+rand()%(500);for(inti=1;i〈=100;i++)cout〈〈data[i]〈〈"";cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";for(inti=0;i〈100;i++)while(1){cout〈〈"0：快速排序\n";cout〈〈"1:希尔排序\n";cout〈〈"2:二路归并排序\n";cout〈〈"3:堆排序\n";cout〈〈"4：退出\n";cout〈〈"请输入(0--4):\n"cin>>c;switch(c){case0:QuickSort(data,1,100);cout〈〈"快速排序后的序列为:"〈〈endl;for(inti=1;i〈=100;i++){cout〈〈data[i]〈〈"";}cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";break;case1:ShellSort(data,100);cout〈〈"希尔排序后的序列为:"〈〈endl;for(inti=1;i〈=100;i++){cout〈〈data[i]〈〈"";}cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";break;case2:MergeSort(data,data1,100);cout〈〈"二路归并排序后的序列为:"〈〈endl;for(inti=0;i〈100;i++){cout〈〈data[i]〈〈"";}cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";break;case3:heapsort(data,100);cout〈〈"堆排序后的序列为:"〈〈endl;for(inti=1;i〈=100;i++){cout<<data[i]<<"";}cout<<endl;break;case4:return0;break;}}return0;}六、程序测试与实现1、主程序voidmain()//{intdata[101],data1[101],data2[100],c;cout〈〈"随机产生个随机数为"〈〈endl;for(inti=1;i<=100;i++)data[i]=10+rand()%(500);for(inti=1;i〈=100;i++)cout〈〈data[i]〈〈"";cout〈〈endl;cout〈〈setfill('*')〈〈setw(80)〈〈"*\n";for(inti=0;i〈100;i++)while(1){cout〈〈"0：快速排序\n";cout〈〈"1:希尔排序\n"cout〈〈"2:二路归并排序\n"cout〈〈"3:堆排序\n"cout〈〈"4：退出\n";cout〈〈"请输入(0--4): \n";cin>>c;}3、测试数据i阴个随机数为題MiillW織iBf曲量眶W徳琏丫龜诙腫f繞rut旳8肾■嘶甲*tlMMif；y-£jt-Miiit-MMflcMl?l»g}M»MiTSlfcWtMjlffMM：MBWM■umtijyw』;wwwm?1乂・2674736?2332513?38S336S16ill4335848128?243?51454S421328S3264513?133?4星并排非'■■-序速奮番曙二堆退4、测试结果二塔归并排序后的序列为:GHGi&1G3?45454747484850ElE11511541552512632&G34435335244144&4491581S31721741771791832672742812883633683693784524524544GG2912583@23793S03S64G74£4471E758929430?3?24722133154朗4?4215318401476ill221321403477114嘟二塔归并排序后的序列为:GHGi&1G3?45454747484850ElE11511541552512632&G34435335244144&4491581S31721741771791832672742812883633683693784524524544GG2912583@23793S03S64G74£4471E758929430?3?24722133154朗4?4215318401476ill221321403477114嘟32&4044SS1162233324跖501128233333412133234337422126236337431139239343439Xcl[Bj：]sei485332228倔4043262264774033212214764813182154744S83152134723?2

36?2能47138G3821834&4鈿砂2¥817?4573?9291

1??4563?82881?44543692811724b23682?41S345236026?15844935226615544e35626315444134425115143934323913943133?236136422337234133949258S?5151504S4S474745453916IS肉速排序后的序列対2细.1639454547474849；>0515157■5892:94ill1141161281331361391511541551581631721741??1??1832S0213215221226228233234Z36239251迪266267274281Z昵2?12?83K23R9315313321326