比较冒泡排序和快速排序的时间性能.doc

文档介绍：南华大学
计算机科学与技术学院
实验报告
( 2010 ~2011学年度第二学期)
课程名称
算法设计与分析
实验名称
比较冒泡排序
与快速排序的时间性能
姓名
陈亮
学号
20094100104
专业
数媒
班级
091
地点
8-212
教师
刘立

比较冒泡排序与快速排序的时间性能。


利用随机数产生函数获取数据;
分别用两种不同的排序方法对数据进行排序;
用记时函数对两张排序算法分别进行记时;
用十组以上数据进行实验(10~10000)。

#include<>
#include<>
#include<>
#define MAX 2000 // 元素个数
#define NUM_MAX 100000 // 随机数的最大值+1
int Partition(int a[],int n,int low,int high)//快速寻找分界点
{ int pivotkey,t;
pivotkey=a[low];
while(low<high)
{
while(low<high&&a[high]>=pivotkey)
high--;
t=a[low];
a[low]=a[high];
a[high]=t;
while(low<high&&a[low]<=pivotkey)
low++;
t=a[low];
a[low]=a[high];
a[high]=t;
}
return low;
}
void QSort(int a[],int n,int low,int high)//快速排序
{ int pivotloc;
if(low<high)
{
pivotloc=Partition(a,n,low,high);
QSort(a,pivotloc,low,pivotloc-1);
QSort(a,high-pivotloc,pivotloc+1,high);
}
}
void HeapAdjust(int a[],int s,int m)
{
int rc = a[s];
int j=0;
for(j=2*s+1;j<=m;j=j*2+1)
{
if(j<m && a[j] < a[j+1])
++j;
if(rc > a[j])
break;
a[s] = a[j];
s = j;
}
a[s] = rc;
}
void BubbleSort(int a[],int n)//冒泡排序
{ int t,i,j;
for(j=1;j<=n-1;j++)
for(i=1;i<=n-j;i++)
if(a[i-1]>a[i])
{
t=a[i-1];
a[i-1]=a[i];
a[i]=t;
}
}
int main()
{
srand(time(00));
int i,a[MAX];
clock_t begin, end;
double cost;
for(i=0;i<MAX;i++)
a[i]=rand()%NUM_MAX;
begin = clock();
BubbleSort(a