算法时间复杂度.docx

文档介绍：实验一 算法的时间复杂度
实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对算法分析基础知识的理解。
实验内容 :
掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。
实验题
定义一个足够大的整型数组， 并分别用起泡排序、 简单选择排序、 快速排序和归并排序对数
组中的数据进行排序(按从小到大的顺序排序) ，记录每种算法的实际耗时，并结合数据结
构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：
、数组中的数据随机生成；
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=Par