冒泡排序和快速排序实验报告.doc

实验报告实验名称 实验三 冒泡排序和快速排序 班 级 学 号 姓 名 成 绩 实验概述： 【实验目的及要求】实验目的：通过编程程序达到熟悉并掌握教材中所介绍的几种排序方法。实验要求：1）随机产生20位整数2）输入序列，编写程序，按下列排序方法将序列从小到大排序并输出。1. 冒泡排序2. 快速排序3）纪录每种方法比较次数和移动次数4）随机产生2000位整数，重做实验2），比较两种算法需要的计算时间。【实验原理】1 随机产生20位整数 随机数的产生见实验一。创立一个数组，将产生的随机数存入数组。2 冒泡排序对于带排序的数组L（n），使用冒泡排序的算法如下：输入：数组L（n）（无序）输出：数组L（n）（有序）f=1While (f0) Dok=f+1; f=0;For j=n To k Step -1 If L(j-1)L(j) Then T=L(j); L(j)=L(j+1); L(j+1)=T; f=j; 3 快速排序对于带排序的数组P（n），使用快速排序的算法如下：输入：待排序的子表P(m：n)。输出：有序子表P(m：n)。PROCEDURE QKSORT1(P，m，n)IF (nm) THEN 子表不空 SPLIT(P，m，n，i)； 分割 QKSORT1(P，m，i1)；对前面子表进行快速排序 QKSORT1(p，i1，n)；对后面子表进行快速排序 RETURN4 纪录每种方法比较次数和移动次数设变量X，Y，记录上面算法比较和移动的次数。5 关于计算时间的比较使用GetTickCount来记录算法使用时间，具体算法如下：DWORD start_time;DWORD end_time; DWORD run_time; start_time = GetTickCount();算法（）;end_time = GetTickCount();run_time = end_time - start_time;【实验环境】（使用的软硬件）1硬件：笔记本。2软件：Window XP、Turbo C 3.0实验内容：【实验方案设计】冒泡法排序的程序如下：#include#include#define N 20int comp=0,move=0;main()long m=65536;long y=0;int xN,i=0,j,temp;printf(nmao pao fa pai xu:n);printf(zui chu chan sheng de sui ji shu:n); for(;iN;i+) y=(2053*y+13849)%m;xi=(int)(1000*y/m); printf(%dt,xi); for(j=0;jj;i-) comp+; if(xi-1xi)temp=xi;xi=xi-1;xi-1=temp;move+;printf(npai hao hou de sui ji shu:n);for(i=0;iN;i+)printf(%dt,xi);printf(nmove=%d,comp=%d,move,comp); 快速法的程序如下：#include#include#include#define N 20int comp=0,move=0;main()void kuaisu(int x,int left,int right);long m=65536;long y=0;int xN,i=0,j,temp,left=0,right=N-1;printf(nkuai su fa pai xu:n);printf(zui chu chan sheng de sui ji shu ru xia:n); for(;iN;i+) y=(2053*y+13849)%m;xi=(int)(1000*y/m); printf(%dt,xi); printf(n);kuaisu(x,left,right);printf(yong kuai su fa pai hao hou de shu:n);for(i=0;iright)return; while(i!=j) comp+; while(xj=temp & ji) j-; if(ji) xi+=xj; move+; while(xii) i+; if(ji) xj-=xi; xi=temp;kuaisu(x,left,i-1);kuaisu(x,i+1,right);【实验过程】（实验步骤、数据、分析）实验步骤：1）随机产生20位整数2）输入序列，编写程序，按下列排序方法将序列从小到大排序并输出。1. 冒泡排序2. 快速排序3）纪录每种方法比较次数和移动次数实验结果分析：根据冒泡法和快速法输出地移动次数和比较次数可以看出，快速法的移动次数和比较次数要比冒泡法少许多。因此，快速法是一种比冒泡法更好的排序法。【结论】（结果）冒泡法排序的结果的截图：快速法排序的结果的截图：【小结】由于大一下学期学习C语言时，冒泡法和快速法都是重点内容，这次实验进行的比较顺利，没有遇到太多困难。只是刚开始不知道怎样输出比较次数和移动次数，后来定义了两个全程变量，解决了这个问题。另外，虽然实验说明上