算法时间复杂度 The final edition was revised on December 14th, 2020.
实验一算法的时间复杂度
一、实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对算法分析基础知识的理解。
二、实验内容:
掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。
三、实验题
定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。
实验数据分两种情况：
1、数组中的数据随机生成；
2、数组中的数据已经是非递减有序。
四、实验步骤
理解算法思想和问题要求；
编程实现题目要求；
上机输入和调试自己所编的程序；
验证分析实验结果；
整理出实验报告。
五、实验程序
#include<iostream>
#include<>
#include<>
using namespace std;
void SelectSort(int r[ ], int n)
{
int i;
int j;
int index;
int temp;
for (i=0; i<n-1; i++)
{
index=i;
for (j=i+1; j<n; j++)
if (r[j]<r[index])
index=j;
if (index!=i)
{
temp=r[i];
r[i]=r[index];
r[index]=temp;
}
}
for(i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<"\n";
}
void BubbleSort(int r[], int n)
{
int temp;
int exchange;
int bound;
exchange=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;
}
}
for(int i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<"\n";
}
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()%100;
cout<<b[k]<<" ";
cout << "\n起泡排序结果为：" << "\n";
BubbleSort(b, numv);
cout<<clock()-t<<"ms"<<endl;
cout<<"\n 简单选择排序结果为："<<"\n";
SelectSort(b, numv);
cout<<clock()-t<<"ms"<<endl;
cout<<"\n 快速排序结果为："<<"\n";
QuickSort(b,0,100);
for(int j=0;j<100;j++)
cout<<b[j]<<" ";
cout<<"\n";
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<<"\n 归并排序结果为："<<"\n";
MergeSort2(b1,a1,c1,0,h-1);
for(int m=0; m < h; m++)
cout<<a1[m]<<" ";
cout<<"\n";
cout<<(clock()-t)<<"ms"<<endl;
return 0;
}
六实验结果
当随机数为10时：
起泡排序结果为：4ms
简单选择排序结果为：7ms
快速排序结果为：12ms
归并排序结果为：16ms
当随机数为100时：
起泡排序结果为：20ms
简单选择排序结果为：41ms
快速排序结果为：61ms
归并排序结果为：82ms
当随机数为1000时：
起泡排序结果为：289ms
简单选择排序结果为：480ms
快速排序结果为：720ms
归并排序结果为：993ms
七、实验分析
通过本实验知道了最快排序的方法，明白了各种排序法的时间复杂度。