内部排序算法实现与比较.doc

实验四：内部排序算法实现与比较1） 问题描述在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2）基本要求(1) 对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序。(2) 利用随机函数产生n（如30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。(3) 对结果作出简要分析。3）测试数据随机函数产生。4）提示主要工作是设法在已知算法中适当位置插入对关键字的比较次数和移动次数的计数操作。注意采用分块调试的方法。5）输入输出:输入数据：参加排序的整数个数n（如n=30000）；输出数据：各种排序方法的关键字比较次数和移动次数（从小到大排列）。二、概要设计写出要求的排序算法，然后对各个算法进行比较，算出它们的复杂度。三、源程序#include#include#define N 8 / 用来存排序用的数据，其中第一个元素经常作为哨兵和交换用int change5,compare5;/分别用来描述排序所交换的趟数和比较的趟数从第二个 元素开始使用int p=0;void insretsort(int s)int i,j;int sum=0;int a8;for(i=1;iN;i+)ai=si;for (i=2;iN;i+)a0=ai;for(j=i-1;a0aj;)compare0+;aj+1=aj;change0+;j-;aj+1=a0;change0+;sum+;printf(第%d 排序结果是：,sum);for(int i=1;iN;i+)printf(%5d,ai);printf(一共进行了%d 比较,compare0);printf(一共进行了%d 交换,change0);void bubblesort(int s)int i=1,j,k,m,done=1;int a8;for(m=1;mN;m+)am=sm;while(iN&done)done=0;for(j=1;jN-i;j+)if(aj+1aj)a0=aj;aj=aj+1;aj+1=a0;done=1;change1=change1+3;printf(第%d 趟的结果是：,i);for(k=1;kN;k+)printf(%5d,ak);printf(n);compare1+;i+;printf(冒泡排序一共经过了%d 交换：,compare1);printf(冒泡排序一共经过了%d 比较：,change1);printf(最终排序结果是：n);for(k=1;kN;k+)printf(%5d,ak ); printf(n);void simplesssort(int s)int i,j,k,sum=0;int a8;for(i=1;iN;i+)ai=si;for(i=1;i=N-1;i+)k=i;for(j=i+1;jN;j+)if(ajak)k=j;compare2+;if(k!=i)a0=ak;ak=ai;ai=a0;change1=change1+3;sum+;printf(输出第%d 趟排序的结果：,sum);for(int i=1;iN;i+)printf(%6d,ai);printf(n);printf(一共进行了%d 比较:,compare2);printf(一共进行了%d 交换:,change2);void q_sort(int s,int left,int right)int i=left,j=right;if(ij) s0=si;dowhile(i=s0)j-;if(ij)si=sj;compare3+;i+; while(ij &si=s0) i+;if(ij)sj=si;compare3+;j-;p+;printf(第%d 趟的结果是：,p);for(int c=1;cN;c+)printf(%5d,sc);printf(n);change3+;while(ij);si=s0;printf(n);q_sort(s,left,j-1);q_sort(s,j+1,right);void merges(int s,int s1,int m,int n,int h)/ 一次归并int i,j,k,t;k=i=m;j=n+1; while(i=n & j=h)if(si=sj)s1k=si;i+;elses1k=sj;j+;k+;if(i=m)for(t=i;t=m;t+)s1k+t-i=st;elsefor(t=j;t=h;t+)s1k+t-j=st;void mergepass(int sN,int s1N,int len)/一趟归并int i,j;i=1;while(i=N-2*len+1)merges(s,s1,i,i+len-1,i+2*len-1);i=i+2*len;if(i+len-1N)merges(s,s1,i,i+len-1,N-1);elsefor(j=i;jN;j+)s1j=sj; void mergesort(int sN)int a8;int g;for(g=1;gN;g+)ag=sg;int len;int s18;len=1;while(lenN-1)mergepass(a,s1,len);len=2*len;p+;printf(输出归并排序第%d 的结果:n,p);for(int l=1;lN;l+)printf(%6d,s1l);printf(n);change4+;mergepass(s1,a,len);len=2*len;p+;printf(输出归并排序第%d 的结果:n,p);for(g=1;gN;g+)printf(%6d,ag);printf(n);len=2*len;change4+;printf(一共进行了%d 比较：,compare4);printf(一共进行了%d 交换：,change4);/mergesort end/归并函数结束/void main() int i,j,sN;printf(1、选择法排序n);printf(2、冒泡法排序n);printf(3、直接插入法排序n);printf(4、快速排序n);printf(5、两路合并法排序n);printf(7、退出排序比较程序n);printf(随机产生的数据:n);for(i=1;iN;i+)si=rand()%100;printf(%6dn,si);doprintf(选择菜单：);printf(n);printf(1、选择法 ,2、冒泡法 ,3、插入法 ,4、快速法 , 5、两路合并法 ,6、退出n);scanf( %d,&j);switch(j)case 1:printf(用选择法排序结果为:);simplesssort(s);break;case 2: printf(用冒泡法排序结果为：); bubblesort(s);break;case 3:printf(用直接插入法排序结果为：);insretsort(s);break;case 4:printf(用快速法排序结果为：);q_sort(s,1,N-1);break;case 5:printf(用两路合并法排序结果为：);mergesort(s);break;case 6:exit(0);break;while(1);选择法O() 冒泡法O() 直接插入法O() 快速排序法O() 两路合并法O(nlogn)四、 算法描述：希尔排序：Shell排序又称缩小增量排序，属插入类排序法，它的基本思想是：先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。Shell是针对普通插入排序的缺陷进行的改进。快速排序：快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排记录分割成两部分，其中一部分记录的关键字均比另一部分的小，则可分别对这两部分记录进行递归快速排序。堆 排 序：堆排