算法时间复杂度分析：排序

算法复杂度分析

作业内容：

选择两个以上（含两个）解决同一个问题的算法，以相同的数据作为输入，分析在自己电脑上实际运行时间，对不同算法时间复杂度的事前分析进行验证。验证方案与数据自行设计（注意数据规模，如果数据规模太小可能监测不到耗时，另外注意递归算法，递归次数太多也可能没有结果和时间输出）。 比如：选择三种排序算法，对同一组初始数据进行排序，检测每种算法排序时所消耗的时间，查看结果是否与已知的算法时间复杂度分析相符。

作业请以一个word或wps格式的文档作为附件提交，文档包含三部分内容：方案设计、程序代码（粘贴入文档中）、运行结果及分析。 作业思路：

先利用随机数函数生成大量数据，再通过调用 time.h 中的 clock() 函数，及CLOCK_PRE_SECOND 值，对程序运行时间进行计算，之后对算法进行复杂度分析。 所选算法：

冒泡排序、快速排序 随机数生成： 代码：

#include #include #include #include

using namespace std;

int main() { freopen(\ srand(time(NULL)); int t=100; while(t--) { int n; n=1000; printf(\ for(int i=0;i

冒泡排序：

#include #include #include #include

#define MAX_N 100100

using namespace std;

int a[MAX_N];

int main() { long long start,finish; freopen(\ freopen(\ int n; start=clock(); while(~scanf(\ { for(int i=0;ia[j+1]) { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(int i=0;i

}

return 0;

快速排序：

#include #include #include #include

#define MAX_N 100100

using namespace std;

int a[MAX_N];

void quick(int l, int r) { if (l< r) { int i = l, j = r, x = a[l]; while (i < j) { while(i < j && a[j]>= x) j--; if(i < j) a[i++] = a[j]; while(i < j && a[i]< x) i++; if(i < j) a[j--] = a[i]; } a[i] = x; quick(l, i - 1); quick(i + 1, r); } }

int main() { long long start,finish; freopen(\ freopen(\ start=clock();

}

int n;

while(~scanf(\{ for(int i=0;i

finish=clock();

printf(\return 0;

结果截图：

1

data.cpp：