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

南华大学计算机科学与技术学院实验报告（2010~2011学年度第二学期）课程名称算法设计与分析实验名称比较冒泡排序

与快速排序的时间性能姓名陈亮学号20094100104专业数媒班级091地点8-212教师刘立1.实验目的比较冒泡排序与快速排序的时间性能。利用随机数产生函数获取数据；分别用两种不同的排序方法对数据进行排序；用记时函数对两张排序算法分别进行记时；用十组以上数据进行实验（10~10000）。#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#defineMAX2000//元素个数

#defineNUM_MAX100000//随机数的最大值+1

intPartition(inta[],intn,intlow,inthigh)//快速寻找分界点

{intpivotkey,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;

}

returnlow;

}voidQSort(inta[],intn,intlow,inthigh)//快速排序

{intpivotloc;

if(low<high)

{

pivotloc=Partition(a,n,low,high);

QSort(a,pivotloc,low,pivotloc-1);

QSort(a,high-pivotloc,pivotloc+1,high);

}

}

voidHeapAdjust(inta[],ints,intm)

{

intrc=a[s];

intj=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;

}

voidBubbleSort(inta[],intn)//冒泡排序

{intt,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;

}

}intmain()

{

srand(time(00));

inti,a[MAX];

clock_tbegin,end;

doublecost;for(i=0;i<MAX;i++)

a[i]=rand()%NUM_MAX;

begin=clock();

BubbleSort(a,MAX);

end=clock();

cost=(double)(end-begin)/CLOCKS_PER_SEC;

printf("冒泡排序用时为：%lf秒\n",cost);begin=clock();

QSort(a,MAX,0,MAX-1);

end=clock();

cost=(double)(end-begin)/CLOCKS_PER_SEC;

printf("快速排序用时为：%lf秒\n",cost);return0;

}

元素个数为10的结果截图元素个数为200的结果截图元素个数为500的结果截图元素个数为1000的结果截图元素个数为2000的结果截图元素个数为4000的结果截图元素个数为6000的结果截图元素个数为8000的结果截图元素个数为9000的结果截图元素个数为9500的结果截图实验数据表102005001000200040006000800090009500冒泡排序快速排序实验数据曲线图实验结论：从以上数据表和数据曲线图均可以看出，在元素个数比较小的情况下，两者的时间性能区分不是很明显。但当元素个数比较大的情况下，快速排序的时间性能明显优于冒泡排序的时间性能。由此可以得出结论：快速排序的时间性能优于冒泡排序的时间性能。（在实验中遇到了一个问题，就是当元素个数超过9500的时候，只能显示冒泡排序的执行时间，而没有显