算法的时间复杂度 实验报告

实验一 算法的时间复杂度

一、 实验目的与要求

熟悉C/C++语言的集成开发环境；

通过本实验加深对算法分析基础知识的理解。 软件环境： 操作系统：windows7 旗舰版

集成开发环境 ：visual studio 2010 旗舰版 硬件环境： 处理器：因特尔 Core i3 M 380 内存： 2GB

二、 实验内容:

掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。

三、 实验题

定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：

1、数组中的数据随机生成；

2、数组中的数据已经是非递减有序。

四、 实验步骤

理解算法思想和问题要求； 编程实现题目要求；

上机输入和调试自己所编的程序；

验证分析实验结果； 整理出实验报告。

五、 实验程序

#include #include #include

#include //导入时间库函数文件 using namespace std;

void BubbleSort(int arr[],int n);

void QuickSort(int arr[],int left,int right); void SelectSort(int arr[],int n);

void UnionSort(int arr[],int left,int right); int Partition(int arr[],int left,int right);

void Union(int arr[],int left,int mid,int right);

const int ARRAY_MAXSIZE=10000; //定义数组最大长度

int main(int argc,char *argv[]){ //测试调用的排序算法耗时 int array_Sort[ARRAY_MAXSIZE]; //声明待排序的数组 int array_Sort2[ARRAY_MAXSIZE];

for(int i=0;i<=ARRAY_MAXSIZE;i++){ //生成随机数组，大小为10000 array_Sort[i]=rand()P0; }

for(int j=0;j

clock_t start,end; //声明开始和结束的时间计数器 start=clock(); //排序开始时间计数器

BubbleSort(array_Sort,ARRAY_MAXSIZE); //起泡排序算法测试 end=clock(); //排序结束时间计数器 cout<<\随机数组起泡排序测试耗时为：\ cout<<(double)(end-start)<<\

start=clock();

QuickSort(array_Sort,0,ARRAY_MAXSIZE-1); //快速排序算法测试 end=clock(); cout<<\随机数组快速排序测试耗时为：\ cout<<(double)(end-start)<<\

start=clock();

SelectSort(array_Sort,ARRAY_MAXSIZE); //选择排序算法测试 end=clock(); cout<<\随机数组选择排序测试耗时为：\ cout<<(double)(end-start)<<\

start=clock();

UnionSort(array_Sort,0,ARRAY_MAXSIZE-1); //归并排序算法测试

end=clock(); cout<<\随机数组归并排序测试耗时为：\ cout<<(double)(end-start)<<\

cout<

start=clock();

BubbleSort(array_Sort,ARRAY_MAXSIZE); end=clock(); cout<<\非递减数组起泡排序测试耗时为：\ cout<<(double)(end-start)<<\

start=clock();

QuickSort(array_Sort,0,ARRAY_MAXSIZE-1); end=clock(); cout<<\非递减数组快速排序测试耗时为：\ cout<<(double)(end-start)<<\

start=clock();

SelectSort(array_Sort,ARRAY_MAXSIZE); end=clock();

cout<<\非递减数组用选择排序测试耗时为：\ cout<<(double)(end-start)<<\

start=clock();

UnionSort(array_Sort,0,ARRAY_MAXSIZE-1); end=clock();

cout<<\非递减数组用归并排序测试耗时为：\ cout<<(double)(end-start)<<\

system(\ return 0; }

//起泡排序的定义，需要两个参数待排数组和数组长度 void BubbleSort(int arr[],int n) {

int exchange=n; //记录本次交换的位置 int bound=0; //每次待排序的到的位置

int temp=0; //临时变量存储交换时的一个值 while(exchange){ bound=exchange; exchange=0;

for(int i=0;i

if(arr[i]>arr[i+1]){ //判断最近两个并做交换 temp=arr[i];

arr[i]=arr[i+1]; arr[i+1]=temp;

exchange=i; //for循环结束时记录的是本趟循环最后交换的位置 } } } }

//快速排序的定义，需要三个参数待排序数组、数组左边界和右边界 void QuickSort(int arr[],int left,int right) {

if(left

QuickSort(arr,left,pivot-1); //递归对划分后的左侧快速排序 QuickSort(arr,pivot+1,right); //递归对划分后的又侧快速排序 } }

//选择排序的定义，需要两个参数待排序数组和数组长度 void SelectSort(int arr[] ,int n) {

int index=0; //记录每次比较中的较小数的位置 int temp=0; //交换时的临时变量 for(int i=0;i

index=i; //默认每次循环时第一个为最小 for(int j=i+1;j<=n;j++){ if(arr[j]

if(index!=i){ //如果当前的最小值不是arr[i],则和记录位置的值交换 temp=arr[i];

arr[i]=arr[index]; arr[index]=temp; } } }

//归并排序的定义，需要三个参数待排序数组、数组左边界和右边界 void UnionSort(int arr[],int left,int right) {

if(left

Union(arr,left,mid,right); //将两个有序序列合并成一个有序的序列