算法设计实验报告一

1、计算机算法设计与分析实 验 报 告实验名称：排序算法效率比较实验地点：所使用的开发工具及环境：1、 实验目的：比较至少4种排序算法的执行效率。已学过的算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等。二、实验内容：1、从中选择至少4中排序算法，写成独立的函数进行调用。2、参与排序的数据不少于10000个，要求用数据文件存储随机产生的数据。3、要求在main()函数中调用以上函数，并输出各排序算法所用时间。3、 基本思想、原理和算法描述： 本次实验要求写出四种算法，来比较它们运行的时间。冒泡排序：总的时间复杂度为O(n).基本思想：首先将第一个记录的关键字和第二个记录的关

2、键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第n-1和第n个的关键字进行比较为止。算法描述：void BubbleSort(int r,int length) /冒泡排序int i,j,temp;for(j=length;j>0;j-)for(i=0;i<j-1;i+)if(ri>ri+1)temp=ri;ri=ri+1;ri+1=temp; 简单选择排序：总的时间复杂度为O(n2)基本思想：通过n-i次关键字的比较，从n-i+1个记录中选取出关键字最小的记录并和第i个记录交换。算法描述：void SelectSort(in

3、t r,int length) /简单选择排序int i,j,k;int x; for (i=1;i<=length-1;+i)k=i;for(j=i+1;j<=length;+j)if(rj<rk)k=j;if( k!=i)x= ri;ri=rk;rk=x;插入排序：总的时间复杂度为：O(n2)算法描述：void InsertSort(int r,int length) /插入排序int i,j;for (i=0;i<=length;i+)r0=ri;j=i-1;while(r0<rj)rj+1=rj;j=j-1;rj+1=r0;快速排序：总的时间复杂度为O(n

4、log2n)基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分的记录继续进行排序，直到整个序列有序。算法描述：void QuickSort(int A,int low,int r)/快速排序if(low<r)int high = Partition(A,low,r); QuickSort(A,low,high-1);QuickSort(A,high+1,r);4、 源程序清单：#include<stdio.h>#include<stdlib.h>#include<time.h>#includ

5、e<windows.h>#define MAX 10000void BubbleSort(int r,int length) /冒泡排序int i,j,temp;for(j=length;j>0;j-)for(i=0;i<j-1;i+)if(ri>ri+1)temp=ri;ri=ri+1;ri+1=temp; void SelectSort(int r,int length) /简单选择排序int i,j,k;int x;for (i=1;i<=length-1;+i)k=i;for(j=i+1;j<=length;+j)if(rj<rk)k=j

6、;if( k!=i)x= ri;ri=rk;rk=x; void InsertSort(int r,int length) /插入排序int i,j;for (i=0;i<=length;i+)r0=ri;j=i-1;while(r0<rj)rj+1=rj;j=j-1;rj+1=r0;int Partition(int A,int low,int high)int i,j,x,t;x = Ahigh;i = low-1;for (j = low;j<=high;j+)if(Aj < x)i+;t = Aj;Aj = Ai;Ai = t; Ahigh = Ai+1;Ai+

7、1 = x; return i+1;void QuickSort(int A,int low,int r)/快速排序if(low<r)int high = Partition(A,low,r); QuickSort(A,low,high-1);QuickSort(A,high+1,r);void main()long iStart,iStop,runtime;int numMAX, aMAX;int i,j;iStart=GetTickCount();srand(unsigned)time(NULL);for(i=0;i<MAX;i+)numi=rand();iStop=GetTi

8、ckCount();runtime=iStop-iStart;printf("生成%d个随机数用了%ldmsn",MAX, runtime);printf("-n");for(i=0;i<MAX;i+)ai=numi;iStart=GetTickCount();BubbleSort(a,MAX);iStop=GetTickCount();runtime=iStop-iStart;printf("使用冒泡排序用了%ldmsn",runtime);for(i=0;i<MAX;i+)ai=numi;iStart=GetTickC

9、ount();SelectSort(a,MAX);iStop=GetTickCount();runtime=iStop-iStart;printf("使用简单选择排序用了%ldmsn",runtime);for(i=0;i<MAX;i+)ai=numi;iStart=GetTickCount();InsertSort(a,MAX);iStop=GetTickCount();runtime=iStop-iStart;printf("使用插入排序用了%ldmsn",runtime);for(i=0;i<MAX;i+)ai=numi;iStart=GetTickCount();QuickSort(a,1,MAX);iStop=GetTickCount();runtime=iStop-iStart;printf("使用快速排序用了%ldmsn",runtime); 5、 程序运行结果（包括上机调试的情况、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，对执行结果进行分析。）： 最主要的就是怎样产生不同的随机数，并且还要记录下排序前后的时间。最后就是在快速排序的时候有点问题。不过经过查资料和多次调试，问题基本得到解决六、实验总结： 在本次实验中要求