文档介绍：《数据结构》
课程设计报告书
题目: 冒泡排序算法性能分析
系别: 计算机科学与应用系
学号:
学生姓名: 索琳琳
指导教师: 薛海燕
完成日期: 2010年6月14日
冒泡排序算法性能分析
需求分析
首先,定义一个数组,规定其最大的存储量是10000
数据输入部分,要求用户能从屏幕上输入要测试的数目num,例如num为10。程序通过语句得到这个num,进行分析,如果输入的num<0或者num>10000时,屏幕上提示用户输入错误,请重新输入;如果输入0,表示循环结束;如果数据满足要求程序根据测试的数目num,将随机生成num个无序的数据,并将这些数据存储在数组中。
然后,程序调用自定义函数BubbleSort和时间函数,进行冒泡排序并计算出执行的时间。
最终,输出部分。如果待测试的数目满足要求输出冒泡排序后排序结果及算法执行时间(ms),如果不满足要求输出输入错误,请重新输入。
概要设计
从屏幕输入测试的数目
输入数据num<0或者num>10000
输出显示输入错误请重新输入
输入数据满足要求,调用rand()函数,随机生成数据,存储在数组中
显示结果
调用冒泡排序函数和时间函数,进行冒泡排序和算法执行时间
输入数据为0
显示循环结束
判断数据是否符合要求
程序流程可以用以下流程图来刻画:
详细设计
采用VC++,用数组来存储数据,用函数rand()实现随机数的生成,用函数srand()为函数rand()设置随机种子使之产生的不是伪随机种子,用自定义函数BubbleSort实现冒泡排序,用时间函数实现算法执行时间的计算。
冒泡排序的思想描述与算法表示
(1)冒泡排序思想描述
冒泡排序的过程很简单。首先将容量为n的数组中的第一个数据和第二个数据进行比较,若为逆序,则将两个数据交换之,然后比较第二个数据和第三个数据。依次类推,直至第n-1 数据和第n个数据进行过比较为止。上述过程为第一次冒泡排序,其结果使得数据最大的记录安置到数组的第n-1的位置上。然后进行第二次冒泡排序,其结果使得数据次大的记录安置到数组的第n-2位置上。依次类推。整个排序的过程需要进行k(1=<k<n),每次排序就是将最大的数据放在最后,一般地,第i趟冒泡排序是从a[0]到a[n-i]依次比较相邻两个记录的数据,并在“逆序”时交换相邻记录。
(2)冒泡排序算法表示
自定义了函数BubbleSort,实现冒泡排序,用C语言描述如下:
void BubbleSort( int R[],int n)
{
int j,i;
int temp;
for(i=1;i<n;i++)
{
for(j=0;j<n-i;j++)
if(R[j]>R[j+1])
{
temp=R[j];
R[j]=R[j+1];
R[j+1]=temp;
}
}
printf("\n");
}
程序每次执行时需要调用函数rand()产生随机数据,并且调用函数srand()为函数rand()设置随机数种子,使之产生不同的随机数序列。
定义语句用C语言描述如下:
srand(time(NULL)) ; /*用标准库函数srand()为函数rand()设置随机种子, 用计算机读取时钟值并把该值自动设置为随机数种子*/
for(i=0;i<num;i++) /*num为用户想要随机生成的数据的数目*/
{
a[i]=rand(); /*用for循环为数组中的每一个元素随机赋值*/
}
统计在这些数据上程序的执行时间,需要使用库函数中的函数time(),包含在头文件""中。
定义语句C语言描述如下:
double T, start ,end; /*定义变量,代表时间的开始和结束*/
start=clock(); /*调用clock(),记下程序执行的开始时刻*/
BubbleSort(a,num); /*调用自定义函数,进行冒泡排序*/
end=clock(); /*调用clock(),记下程序执行的结束时刻*/
T=(double)(end-start); /*计算程序的执行时间*/
调试分析
在设计过程中主要遇到下列问题:
冒泡排序的思想。通过查阅数据结构课本,知道了冒泡排序的思想就是每趟排序比较相邻两个记录的数据并在“逆序”时交换相邻记录,将最大的数据放在最后。一般地,第i趟冒泡排序是从a[0]到a[n-i]依次比较。
冒泡排序的算法。根据冒泡排序的思想,查阅了C语言书以及数据结构上机实验