发布时间 : 星期日 文章算法的时间复杂度 实验报告更新完毕开始阅读87a00bdf50e2524de5187ec1
实验一 算法的时间复杂度
一、 实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对算法分析基础知识的理解。 软件环境： 操作系统：windows7 旗舰版
集成开发环境 ：visual studio 2010 旗舰版 硬件环境： 处理器：因特尔 Core i3 M 380 内存： 2GB
二、 实验内容:
掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。
三、 实验题
定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：
1、数组中的数据随机生成；
2、数组中的数据已经是非递减有序。
四、 实验步骤
理解算法思想和问题要求； 编程实现题目要求；
上机输入和调试自己所编的程序；
验证分析实验结果； 整理出实验报告。
五、 实验程序
#include
#include
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) {