算法设计实验报告一.doc

《算法设计实验报告一.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第n-1和第n个的关键字进行比较为止。算法描述：voidBubbleSort(intr[],intlength)//冒泡排序{inti,j,temp;for(j=length;j>0;j--)for(i=0;ir[i+1]){temp=r[i];r[i]=r[i+1];r[i+1]=temp;}}简单选择排序：总的时间复杂度为O()基本思想：通过n-i次关键字的比较，从n-i+1

3、个记录中选取出关键字最小的记录并和第i个记录交换。算法描述：voidSelectSort(intr[],intlength)//简单选择排序{inti,j,k;intx;for(i=1;i<=length-1;++i){k=i;for(j=i+1;j<=length;++j)if(r[j]

4、;i++){r[0]=r[i];j=i-1;while(r[0]

5、rt(A,high+1,r);}}四、源程序清单：#include#include#include#include#defineMAX10000voidBubbleSort(intr[],intlength)//冒泡排序{inti,j,temp;for(j=length;j>0;j--)for(i=0;ir[i+1]){temp=r[i];r[i]=r[i+1];r[i+1]=temp;}}voidSelectSort(intr[],in

6、tlength)//简单选择排序{inti,j,k;intx;for(i=1;i<=length-1;++i){k=i;for(j=i+1;j<=length;++j)if(r[j]

7、artition(intA[],intlow,inthigh){inti,j,x,t;x=A[high];i=low-1;for(j=low;j<=high;j++)if(A[j]

8、1,r);}}voidmain(){longiStart,iStop,runtime;intnum[MAX],a[MAX];inti,j