算法设计技能训练报告

1、淮阴工学院算法设计技能训练报告姓名:学号：班级：NIIT学院：计算机与软件工程学院专业：计算机科学与技术题目：排序算法的比较指导教师:目录课题任务描述3系统设计42.1 功能模块设计42.2 数据结构设计62.3 算法设计7详细设计错误!未定义书签。测试8结论10致谢12参考文献13课题任务描述利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。1.1 要求:1.1.1 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。1.1.2 统计每一种排序方法的性能（以

2、上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。1.1.3 如果采用4种或4种以上的方法者，可适当加分。系统设计2.1 功能模块设计世苓0o名俄革也告妙<一砾发豆菌卑世7"碍般£1-SJ_±JL上二送空笈出甑蛇R<、d2.2 数据结构设计intAn;srand(time(0);for(inti=0;i<n;i+)Ai=rand()%n;利用数组A进行生成随机数组然后进行排序structnodeintindex;node*next;；classMyLisprivate:node*head;intlength;利用链表进行排序2.3

3、算法设计1 .直接插入排序原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。2 .希尔排序原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1,最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。1 .冒泡排序原理：将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。要点：设计交换判断条件，提前结束以排好序的序列循环2 .快速排序原理：不断寻找一个序列的中点，然后对中点左右的序列递归的进行排序，直至

4、全部序列排序完成，使用了分治的思想。1.直接选择排序原理：将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，有序区扩大一个，循环最终完成全部排序。.堆排序原理：利用大根堆或小根堆思想，首先建立堆，然后将堆首与堆尾交换，堆尾之后为有序区。归并排序原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。测试gj C; 1,. W ri dm 3 2 me. ?wem 时 金 泡 ro_,.ll 一 !£二IF一 二 bJt, -二二»!ICLIFrFrIT用起快选推僧12345678序- brrrrrEi 入史梨 愿镇 一，誓经臬按

5、JW8图4.1SBC：,Wrdow?7/7：em52me.ewe杳序ILL-Ji ;£pi一 二; IJI- I-J I d ，1 I I I - 隼起居 1.2.3.4.5.6.7.8.主图4.2图4.3(1)平方阶(O(n2)排序一般称为简单排序，例如直接插入、直接选择和冒泡排序；(2)线性对数阶(O(nlgn)排序如快速、堆和归并排序；(3)O(n1+b阶排序£是介于0和1之间的常数，即0<£<1,如希尔排序；(4)线性阶(O(n)排序如桶、箱和基数排序。各种排序方法比较简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

6、影响排序效果的因素因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：待排序的记录数目n；记录的大小(规模)；关键字的结构及其初始状态；对稳定性的要求；语言工具的条件；存储结构；时间和辅助空间复杂度等。不同条件下，排序方法的选择(1)若n较小(如n&50),可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排

7、序。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。排序算法的稳定性1)稳定的：如果存在多个具有相同排序码的记录，经过排序后，这些记录的相对次序仍然保持不变，则这种排序算法称为稳定的。插入排

8、序、冒泡排序、归并排序、分配排序(桶式、基数)都是稳定的排序算法。2)不稳定的：否则称为不稳定的。直接选择排序、堆排序、shell排序、快速排序都是不稳定的排序算法谢我的老师，他们严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；他们循循善诱的教导和不拘一格的思路给予我无尽的启迪。这片论文的每个实验细节和每个数据，都离不开你的细心指导。而你开朗的个性和宽容的态度，帮助我能够很快的融入我们这个新的实验室感谢我的同门，谢谢你们给予我的帮助！感谢我的朋友，感谢你们在我失意时给我鼓励，在失落时给我支持，感谢你们和我一路走来，让我在此过程中倍感温暖！感谢我的家人我的父母、姐姐和弟弟。没有你们，就不会有

9、今天的我！我一直感恩，感恩于我可以拥有一个如此温馨的家庭，让我所有的一切都可以在你们这里得到理解与支持，得到谅解和分担。我爱你们，爱我们的家！一个人的成长绝不是一件孤立的事，没有别人的支持与帮助绝不可能办到。我感谢可以有这样一个空间，让我对所有给予我关心、帮助的人说声谢谢”！今后，我会继续努力，好好工作！好好学习！好好生活！参考文献1刘国钧，陈绍业，王凤翥.图书馆目录.第1版.北京：高等教育出版社，19572傅承义，陈运泰，祁贵中.地球物理学基础.北京：科学出版社，1985,4473华罗庚，王元.论一致分布与近似分析.中国科学，1973（4）:3393574张筑生.微分半动力系统的不变集研究：

10、学位论文，北京：数学系统学研究所，19835BorkoH,BernierCL.Indexingconceptsandmethods.NewYork:AcademicPr,19786机程序设计艺术英文名称：TheArtofComputerProgramming作者：Donald.E.Knuth7.计算机导论名称：IntroductiontoAlgorithms作者：ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordSteinC语言程序设计实用教程全面介绍了C语言的基础知识和程序设计方法，共分为三部分,由浅到深，再到综合应用。第一部分

11、是基础知识的应用，包括第1章到第3章；第二部分为高级知识的应用，包括第4章到第7章；第三部分是综合应用，包括第8章。各章基本知识与典型例题及上机实训紧密结合,每章后面提供了大量的习题。为了满足国家计算机等级考辿的要求，C语言程序设计实用教程介绍了VisualC+6.0的开发环境，教材内容涵盖了全国计算机等级考试考试大纲（C语言程序设计部分）。C语言程序设计实用教程可以作为高职高专各专业学生的教材，也可以作为普通高等院校各专业学生的教材，还可以作为全国计算机等级考试（二级C语言程序设计）的辅导werbyYOZOSOFT代码#include<iostream>#include<f

12、stream>usingnamespacestd;#include<time.h>#include<stdlib.h>#definen2000#definelj20structnodeintindex;node*next;classMyListprivate:node*head;intlength;public:MyList()head=NULL;头指针为空length=0;长度为0MyList()node*left=head;node*right=NULL;while(left!=NULL)right=left;left=left->next;delete

13、right;voidaddNode(intuser_index)if(isEmpty()head=newnode();head->next=NULL;head->index=user_index;else/创建一个新的节点node*newnode=newnode();newnode->index=user_index;newnode->next=NULL;/将节点添加到链表的最末端node*t=head;while(t->next!=NULL)t=t->next;t->next=newnode;length+;intljcode;intgetLengt

14、h()returnlength;voiddisplay()if(isEmpty()cout<<"Thelistisempty!"return;node*temp=head;while(temp)cout<<temp->index;if(!temp->next)/已至链表尾，可以结束输出了。break;cout<<"->"temp=temp->next;cout<<endl;charljcode1;voidlhInput()for(inti=12;i>0;i-)addNode(i

15、);boolisEmpty()if(head=NULL)returntrue;elseintljcode=0;returnfalse;voidbubbleSort()if(isEmpty()intljcode=1;return;/temp指针用来进行指向要交换的两个节点的左边一个node*temp=head;while(temp&&temp->next)if(temp->index>temp->next->index)exchangeNode(temp,temp->next);/尾指针总是指向已经排好的元素的首地址，这里我们先移到链表尾部等待

16、node*tail=head;while(tail->next)tail=tail->next;/外层还是数组的思想，内层就是链表的思想了，/为什么外层要用数组的思想呢？因为这样比较简洁，不易搞错for(inti=0;i<length;i+)temp=head;while(temp->next!=tail)if(temp->index>temp->next->index)exchangeNode(temp,temp->next);tail=temp;/交换相邻两个节点voidexchangeNode(node*left,node*right

17、)/如果left是头结点if(left=head)left->next=right->next;right->next=left;head=right;return;/找到左节点的前一个节点node*before_left=head;while(before_left->next!=left)before_left=before_left->next;before_left->next=right;left->next=right->next;right->next=left;/堆的冒泡排序intljcode2=0;voidpaixu()M

18、yListhengbao;hengbao.lhInput();hengbao.display();hengbao.bubbleSort();hengbao.display();intljcode=0;voidInsertionSort(int*a,intlen)/插入排序函数for(intj=1;j<len;j+)intkey=aj;inti=j-1;intljcode=0;while(i>=0&&ai>key)ai+1=ai;i-;ai+1=key;voidShellSort(int*a,intlen)/希尔排序代码inth=1;while(h<len

19、)h=3*h+1;while(h>0)for(intj=h;j<len;j+)intkey=aj;inti=j-h;while(i>=0&&ai>key)ai+h=ai;i=i-h;intljcode=0;ai+h=key;h=h/3;/冒泡排序voidbubblesort(int*a,intlen)inti,j;for(i=0;i<len-1;i+)for(j=i+1;j<=len-1;j+)if(ai<aj)intt=ai;aj=ai;ai=t;/快速排序voidquickSort(ints,intl,intr)if(l<r)

20、inti=l,j=r,x=sl;while(i<j)while(i<j&&sj>=x)/从右向左找第一个小于x的数j-;if(i<j)si+=sj;while(i<j&&si<x)从左向右找第一个大于等于x的数i+;if(i<j)sj-=si;si=x;quickSort(s,l,i-1);/递归调用quickSort(s,i+1,r);/选择排序voidSelectSort(int*a,intlen)for(inti=0;i<len-1;i+)intk=i;intkey=ai;for(intj=i+1;j<

21、len;j+)if(aj<key)k=j;key=aj;if(k!=i)swap(ai,ak);voidMaxHeapify(int*a,inti,intheapSize)intl=(i+1)*2-1;intr=(i+1)*2;intlargest;if(l<=heapSize&&al>ai)largest=l;elselargest=i;if(r<=heapSize&&ar>alargest)largest=r;if(largest!=i)swap(ai,alargest);MaxHeapify(a,largest,heapSiz

22、e);/创建最大堆voidBuildMaxHeap(int*a,intlen)for(inti=len/2-1;i>=0;i-)MaxHeapify(a,i,len-1);/堆排序voidHeapSort(int*a,intlen)BuildMaxHeap(a,len);for(inti=len-1;i>0;i-)swap(a0,ai);MaxHeapify(a,0,i-1);/归并排序voidmerge(int*data,intp,intq,intr)intn1,n2,i,j,k;int*left=NULL,*right=NULL;n1=q-p+1;n2=r-q;left=(in

23、t*)malloc(sizeof(int)*(n1);right=(int*)malloc(sizeof(int)*(n2);for(i=0;i<n1;i+)/对左数组赋值lefti=datap+i;for(j=0;j<n2;j+)/对右数组赋值rightj=dataq+1+j;i=j=0;k=p;while(i<n1&&j<n2)/将数组元素值两两比较，并合并到data数组if(lefti<=rightj)datak+=lefti+;elsedatak+=rightj+;for(;i<n1;i+)/如果左数组有元素剩余，则将剩余元素合并到d

24、ata数组datak+=lefti;for(;j<n2;j+)/如果右数组有元素剩余，则将剩余元素合并到data数组datak+=rightj;voidmergeSort(int*data,intp,intr)intq;if(p<r)/只有一个或无记录时不须排序q=(int)(p+r)/2);/将data数组分成两半mergeSort(data,p,q);/递归拆分左数组mergeSort(data,q+1,r);/递归拆分右数组merge(data,p,q,r);/合并数组voidoutput(int*A)ofstreamoutput("c:textcode.txt&q

25、uot;,ios_base:out);output<<"数组元素如下："for(inti=0;i<n;i+)output<<Ai<<','output.close();ofstreamoutput1("c:bincode.bin",ios:binary);for(inti=0;i<n;i+)output1<<Ai<<","output1.close();intmain()intAn;srand(time(0);for(inti=0;i<n;i

26、+)Ai=rand()%n;cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"请输入选择:intm;cin>>m;switch(m)case 1:InsertionSort(A,n);output(A);cout<<"已经进行插入排序"<&

27、lt;endl;cout<<"结果已存入文件"<<endl;break;case 2:ShellSort(A,n);output(A);cout<<"已经进行希尔排序"<<endl;cout<<"结果已存入文件"<<endl;break;排序算法的性能"<<endl;1 .插入排序"<<endl;2 .希尔排序"<<endl;3 .起泡排序"<<endl;4 .快速排序"<<endl;5 .选择排序"<<endl;6 .堆排序"<<endl;7 .归并排序"