文档介绍：实验报告
实验名称实验三冒泡排序和快速排序
班级
学号
姓名
成绩
实验概述:
【实验目的及要求】
实验目的:通过编程程序达到熟悉并掌握教材中所介绍的几种排序方法。
实验要求:
1)随机产生20位整数
2)输入序列,编写程序,按下列排序方法将序列从小到大排序并输出。
冒泡排序
快速排序
3)纪录每种方法比较次数和移动次数
4)随机产生2000位整数,重做实验2),比较两种算法需要的计算时间。
【实验原理】
随机产生20位整数
随机数的产生见实验一。创立一个数组,将产生的随机数存入数组。
冒泡排序
对于带排序的数组L(n),使用冒泡排序的算法如下:
输入:数组L(n)(无序)
输出:数组L(n)(有序)
f=1
While (f>0) Do
{ k=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; }
}
}
快速排序
对于带排序的数组P(n),使用快速排序的算法如下:
输入:待排序的子表P(m:n)。
输出:有序子表P(m:n)。
PROCEDURE QKSORT1(P,m,n)
IF (n>m) THEN [子表不空]
{
SPLIT(P,m,n,i); [分割]
QKSORT1(P,m,i-1);[对前面子表进行快速排序]
QKSORT1(p,i+1,n);[对后面子表进行快速排序]
}
RETURN
纪录每种方法比较次数和移动次数
设变量X,Y,记录上面算法比较和移动的次数。
关于计算时间的比较
使用GetTickCount来记录算法使用时间,具体算法如下:
DWORD start_time;
DWORD end_time;
DWORD run_time;
start_time = GetTickCount();
算法();
end_time = GetTickCount();
run_time = end_time - start_time;
【实验环境】(使用的软硬件)
:笔记本。
:Window XP、Turbo C
实验内容:
【实验方案设计】
冒泡法排序的程序如下:
#include<>
#include<>
#define N 20
p=0,move=0;
main()
{long m=65536;long y=0;int x[N],i=0,j,temp;
printf("\nmao pao fa pai xu:\n");
printf("zui chu chan sheng de sui ji shu:\n");
for(;i<N;i++)
{y=(2053*y+13849)%m;x[i]=(int)(1000*y/m);
printf("%d\t",x[i]);
}
for(j=0;j<N-1;j++)
for(i=N-1;i>j;i--)
{comp++;
if(x[i-1]>x[i])
{temp=x[i];x[i]=x[i-1];x[i-1]=