文档介绍：比较起泡排序与快速排序的时间复杂度
一、实验目的与要求
熟悉C/C++语言的集成开发环境;
通过本实验加深对算法分析基础知识的理解。
二、实验内容:
掌握算法分析的基本方法,并结合具体的问题深入认识算法的时间复杂度分析。
三、实验题
以n为参数,对n个随机数分别用起泡排序、快速排序进行排序,记录每种算法的实际耗时,并结合数据结构中的知识对算法的时间复杂度分析进行说明。要求实验数据:
1、数组中的数据随机生成;
2、至少要有10组数据,n分别从10到10000,范围尽量放大,能充分反映算法特点;
3、程序运行界面(包含自己学号与姓名),耗时比较数据,耗时比较曲线。
四、实验代码
:
void BubbleSort(int r[], int n)
{
int temp;
int exchange;
int bound;
exchange=n-1; //第一趟起泡排序的范围是r[0]到r[n-1]
while (exchange) //仅当上一趟排序有记录交换才进行本趟排序
{
bound=exchange;
exchange=0;
for (int j=0; j<bound; j++) //一趟起泡排序
if (r[j]>r[j+1])
{
temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
exchange=j; //记录每一次发生记录交换的位置}
}
2. 快速排序一次划分:
int Partition(int r[], int first, int end)
{
int i=first; //初始化
int j=end;
int temp;
while (i<j)
{
while (i<j && r[i]<= r[j])
j--; //右侧扫描
if (i<j)
{
temp=r[i]; //将较小记录交换到前面 r[i]=r[j];
r[j]=temp;
i++;
}
while (i<j && r[i]<= r[j])
i++; //左侧扫描
if (i<j)
{
temp=r[j];
r[j]=r[i];
r[i]=temp; //将较大记录交换到后面 j--;
}
}
return i; //i为轴值记录的最终位置}
快速排序:
void QuickSort(int r[], int first, int end)
{
if (first<end)
{ //递归结束
int pivot=Partition(r, first, end); //一次划分
QuickSort(r, first, pivot-1);//递归地对左侧子序列进行快速排序 QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序
}
}
:
int main()
{ int n;
time_t first,end;
cou