算法时间复杂度.docx

文档介绍：实验一 算法的时间复杂度
实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对算法分析基础知识的理解。
实验内容 :
掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度
分析。
实验题
定义一个out<<\ ;
}
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;
}
// 快速排序 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);
}
}
void Merge(int r[], int r1[], int s, int m, int t)
{
int i=s;
int j=m+1;
int k=s;
while (i<=m && j<=t)
if (r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
)
if (i<=m)
while (i<=m)
r1[k++]=r[i++];
else
while (j<=t)
r1[k++]=r[j++];
)
void MergePass(int r[ ], int r1[ ], int n, int h)
(
int i=0;
int k;
while (i<=n-2*h)
Merge(r, r1, i, i+h-1, i+2*h-1);
i+=2*h;
if (i<n-h)
Merge(r, r1, i, i+h-1, n);
else for (k=i; k<=n; k++)
r1[k]=r[k];
}
void MergeSort2(int r[], int r1[], int r2[],int s, int t)
{
int m;
if (s==t)
{
r1[s]=r[s];
}
else
{
m=(s+t)/2;
MergeSort2(r, r2, r1, s, m);
MergeSort2(r, r2, r1, m+1, t);
Merge(r2, r1, s, m, t);
int main()
(
int b[100];
const int numv=100;
clock_t t=clock();
for(int k=0;k<100;k++)
b[k]=rand()_x0010_0;
cout<<b[k]<< ;
cout << \
起泡排序结果为：<< \
;
BubbleSort(b, numv);
cout<<clock()-t<<ms<<endl;
cout<<\
简单选择排序结果为：<<\ ;
SelectSort(b, numv);
cout<<clock()-t<<ms<<endl;
cout<<\
快速排序结果为：<<\
QuickSort(b,0,100);
for(int j=0;j<100;j++)
cout<<b[j]<< ;
cout<<\
;
cout<<clock()-t<<ms<<endl;
const int h=100;
int b1[h];
for(int i=0;i<h;i++)
b1[i]=rand()%k;
int a1[h];
int c1[h];
cout<<\
归并排序结果为：<<\
;
MergeSort2(b1,a1,c1,0,h-1);
for(int m=0; m < h; m++)
cout<<a1[m]<< ;
cout<<\
cout<<(clock()-t)<<ms<<endl;
return 0;
}
六 实验结果
当随机数为 10 时：
起泡排序结果为：4ms
简单选择排序结果为： 7ms
快速排序结果为：12ms