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

1、.实验一算法的时间复杂度一、实验目的与要求熟悉 C/C+ 语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。软件环境：操作系统： windows7旗舰版集成开发环境：visual studio 2010旗舰版硬件环境：处理器：因特尔Core i3 M 380内存：2GB二、实验内容 :掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、 快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况：

2、1、数组中的数据随机生成；2、数组中的数据已经是非递减有序。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。'.五、实验程序#include<Windows.h>#include<stdio.h>#include<iostream>#include<time.h>/导入时间库函数文件using namespace std;void BubbleSort(int arr,int n);void QuickSort(int arr,int left,int right);v

3、oid 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_SortARRAY_MAXSIZE;/声明待排序的数组int array_Sort2ARRAY_

4、MAXSIZE;for(int i=0;i<=ARRAY_MAXSIZE;i+)/生成随机数组，大小为10000array_Sorti=rand()%500;for(int j=0;j<ARRAY_MAXSIZE;j+)/生成非递减数组，大小均为10000array_Sort2j=j;clock_t start,end;/声明开始和结束的时间计数器start=clock();/排序开始时间计数器BubbleSort(array_Sort,ARRAY_MAXSIZE);/起泡排序算法测试end=clock();/排序结束时间计数器cout<<" 随机数组起泡排序

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

6、RRAY_MAXSIZE); / 选择排序算法测试 end=clock();cout<<" 随机数组选择排序测试耗时为："cout<<(double)(end-start)<<" ms"<<endl;start=clock();UnionSort(array_Sort,0,ARRAY_MAXSIZE-1);/归并排序算法测试'.end=clock();cout<<" 随机数组归并排序测试耗时为："cout<<(double)(end-start)<&

7、lt;" ms"<<endl;cout<<endl;start=clock();BubbleSort(array_Sort,ARRAY_MAXSIZE);end=clock();cout<<" 非递减数组起泡排序测试耗时为："cout<<(double)(end-start)<<" ms"<<endl;start=clock();QuickSort(array_Sort,0,ARRAY_MAXSIZE-1);end=clock();cout<<&quo

8、t; 非递减数组快速排序测试耗时为："cout<<(double)(end-start)<<" ms"<<endl;start=clock();SelectSort(array_Sort,ARRAY_MAXSIZE);end=clock();cout<<" 非递减数组用选择排序测试耗时为："cout<<(double)(end-start)<<" ms"<<endl;start=clock();UnionSort(array_Sort,0,A

9、RRAY_MAXSIZE-1);end=clock();cout<<" 非递减数组用归并排序测试耗时为："cout<<(double)(end-start)<<" ms"<<endl;system("pause");return 0;/ 起泡排序的定义，需要两个参数待排数组和数组长度void BubbleSort(int arr,int n)int exchange=n;/记录本次交换的位置int bound=0;/每次待排序的到的位置int temp=0;/临时变量存储交换时的一个值w

10、hile(exchange)bound=exchange;exchange=0;for(int i=0;i<bound;i+)if(arri>arri+1)/判断最近两个并做交换temp=arri;'.arri=arri+1;arri+1=temp;exchange=i;/for循环结束时记录的是本趟循环最后交换的位置/ 快速排序的定义，需要三个参数待排序数组、数组左边界和右边界void QuickSort(int arr,int left,int right)if(left<right)/递归结束int pivot=Partition(arr,left,right)

11、;/进行一次划分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<n;i+)index=i;/默认每次循环时第一个为最小for(int j=i+1;j<=n;j+)if(arrj<arrindex)index=j;if(ind

12、ex!=i)/如果当前的最小值不是arri,则和记录位置的值交换temp=arri;arri=arrindex;arrindex=temp;/ 归并排序的定义，需要三个参数待排序数组、数组左边界和右边界void UnionSort(int arr,int left,int right)if(left<right)/序列长度超过一，则进行自序列的划分int mid=(left+right)/2;/将待排序列划分为两部分UnionSort(arr,left,mid);/对左序列进行归并UnionSort(arr,mid+1,right); /对又序列进行归并Union(arr,left,mi

13、d,right);/将两个有序序列合并成一个有序的序列'./ 一次快速排序int Partition(int arr,int left,int right )int i=left;/作为划分中的枢纽值int j=right;/右边界int temp=0;/交换时的临时变量dodo i+;/扫描左侧，当当前位置值大于枢纽值时停止while (arri<arrleft);do j-;/扫描右侧，当当前位置值大于枢纽值时停止while (arrj>arrleft);if(i<j)temp=arri;/交换当前 i 和 j 记录位置的值arri=arrj;arrj=temp;

14、while(i<j) ;/当i<j 时继续 dotemp=arrleft;/i>j时本趟循环结束，交换枢纽值和j 位置的值arrleft=arrj;arrj=temp;return j;/ 归并排序合并两有序的子序列void Union(int arr,int left,int mid,int right)int temp10000;/临时使用的辅助数组int i=left;int j=mid+1;int k=0;while(i<=mid)&&(j<=right)/比较后把 i ， j 中最小的放入temp 中if(arri<=arrj)te

15、mpk+=arri+;else tempk+=arrj+;while(i<=mid)tempk+=arri+;while(j<=right)tempk+=arrj+;for(i=0,k=left;k<=right; )arrk+=tempi+;/把排好序临时数组放回原数组'.六、实验结果1.数组大小 ARRAY_MAXSIZE为 10000 如下：2.数组大小 ARRAY_MAXSIZE为 8000 如下3.数组大小 ARRAY_MAXSIZE为 5000 如下：七、实验分析1、各算法时间时间消耗图'.2、各算法时间性能分析表：方法最好情况最坏情况平均情况起泡排序O(n)O(n)O(n)快速排序O(nlog2n)O(n)O(nlog2n)选择排序O(n)O(n)O(n)归并排序O(nlog2n)O(nlog2n)O(nlog2n)3、分析与说明：由算法时间复杂度表分析，起泡排序在最好情况下时间性能好，最坏情况和平均情况和选择排序一样，选择排序的时间性能都不高，均为 O(n )，根据平均情况来看， 快速排序和归并排序的时间性能一样，且最坏情况时归并排序优于快速排序。对于随机数组序列，数组大小为10000，8000，5