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

南华大学 计算机科学与技术学院 实 验 报 告 （ 2010 ~2011学年度 第 二 学期 ） 课程名称 算法设计与分析 实验名称 比较冒泡排序与快速排序的时间性能 姓名 陈亮 学号 20094100104 专业 数媒 班级 091 地点 8-212 教师 刘立 1.实验目的 比较冒泡排序与快速排序的时间性能。 2.实验内容 利用随机数产生函数获取数据； 分别用两种不同的排序方法对数据进行排序； 用记时函数对两张排序算法分别进行记时； 用十组以上数据进行实验（10~10000）。 3.实验过程 #includestdio.h#includestdlib.h#includetime.h#define MAX 2000 // 元素个数#define NUM_MAX 100000 // 随机数的最大值+1int Partition(int a[],int n,int low,int high)//快速寻找分界点{ int pivotkey,t;pivotkey=a[low];while(lowhigh){while(lowhigha[high]=pivotkey)high--;t=a[low];a[low]=a[high];a[high]=t;while(lowhigha[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(lowhigh){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(jm 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;iMAX;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); return 0;} 元素个数为10的结果截图 元素个数为200的结果截图 元素个数为500的结果截图 元素个数为1000的结果截图 元素个数为2000的结果截图 元素个数为4000的结果截图 元素个数为6000的结果截图 元素个数为8000的结果截图 元素个数为9000的结果截图 元素个数为9500的结果截图 实验数据表 10 200 500 1000 2000 4000 6000 8000 9000 9500 冒泡排序 0.000 0.000 0.000 0.000 0.015 0.093 0.203 0.343 0.437 0.484 快速排序 0.000 0.000 0.000 0.000 0.016 0.032 0.062 0.125 0.156 0.172 实验数据曲线图 实验结论：从以上数据表和数据曲线图均可以看出，在元素个数比较小的情况下，两者的时间性能区分不是很明显。但当元素个数比较大的情况下，快速排序的时间性能明显优于冒泡排序的时间性能。由此可以