《算法的时间复杂度--实验报告》由会员分享，可在线阅读，更多相关《算法的时间复杂度--实验报告（7页珍藏版）》请在金锄头文库上搜索。
1、 实验一 算法的时间复杂度一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对算法分析基础知识的理解。软件环境： 操作系统：windows7 旗舰版 集成开发环境 ：visual studio 2010 旗舰版 硬件环境： 处理器：因特尔 Core i3 M 380 内存： 2GB二、 实验内容:掌握算法分析的基本方法，并结合具体的问题深入认识算法的时间复杂度分析。三、 实验题定义一个足够大的整型数组，并分别用起泡排序、简单选择排序、快速排序和归并排序对数组中的数据进行排序（按从小到大的顺序排序），记录每种算法的实际耗时，并结合数据结构中的知识对算法的时间复杂度分析进行说明。实
2、验数据分两种情况：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,in
3、t 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_MAXSIZE;for(int i=0;i=ARRAY_MAXSIZE;i+) /生成随机数组，大小为
4、10000array_Sorti=rand()%500;for(int j=0;jARRAY_MAXSIZE;j+) /生成非递减数组，大小均为10000 array_Sort2j=j;clock_t start,end; /声明开始和结束的时间计数器start=clock(); /排序开始时间计数器BubbleSort(array_Sort,ARRAY_MAXSIZE); /起泡排序算法测试end=clock(); /排序结束时间计数器cout随机数组起泡排序测试耗时为：;cout(double)(end-start) msendl;start=clock(); QuickSort(arra
5、y_Sort,0,ARRAY_MAXSIZE-1); /快速排序算法测试end=clock(); cout随机数组快速排序测试耗时为：; cout(double)(end-start) msendl;start=clock(); SelectSort(array_Sort,ARRAY_MAXSIZE); /选择排序算法测试end=clock(); cout随机数组选择排序测试耗时为：; cout(double)(end-start) msendl;start=clock(); UnionSort(array_Sort,0,ARRAY_MAXSIZE-1); /归并排序算法测试end=clock
6、(); cout随机数组归并排序测试耗时为：; cout(double)(end-start) msendl;coutendl;start=clock(); BubbleSort(array_Sort,ARRAY_MAXSIZE); end=clock(); cout非递减数组起泡排序测试耗时为：;cout(double)(end-start) msendl;start=clock(); QuickSort(array_Sort,0,ARRAY_MAXSIZE-1); end=clock(); cout非递减数组快速排序测试耗时为：; cout(double)(end-start) msend
7、l;start=clock(); SelectSort(array_Sort,ARRAY_MAXSIZE); end=clock(); cout非递减数组用选择排序测试耗时为：; cout(double)(end-start) msendl;start=clock(); UnionSort(array_Sort,0,ARRAY_MAXSIZE-1); end=clock(); cout非递减数组用归并排序测试耗时为：; cout(double)(end-start) msendl;system(pause);return 0;/起泡排序的定义，需要两个参数待排数组和数组长度void Bubbl
8、eSort(int arr,int n)int exchange=n; /记录本次交换的位置int bound=0; /每次待排序的到的位置int temp=0; /临时变量存储交换时的一个值while(exchange) bound=exchange;exchange=0;for(int i=0;iarri+1) /判断最近两个并做交换 temp=arri;arri=arri+1;arri+1=temp;exchange=i; /for循环结束时记录的是本趟循环最后交换的位置/快速排序的定义，需要三个参数待排序数组、数组左边界和右边界void QuickSort(int arr,int le
9、ft,int right) if(leftright) /递归结束 int pivot=Partition(arr,left,right); /进行一次划分 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;in;i+)index=i;
10、/默认每次循环时第一个为最小for(int j=i+1;j=n;j+)if(arrjarrindex)index=j; if(index!=i) /如果当前的最小值不是arri,则和记录位置的值交换temp=arri;arri=arrindex;arrindex=temp;/归并排序的定义，需要三个参数待排序数组、数组左边界和右边界void UnionSort(int arr,int left,int right)if(leftright) /序列长度超过一，则进行自序列的划分int mid=(left+right)/2; /将待排序列划分为两部分UnionSort(arr,left,mid); /对左序列进行归并UnionSort(arr,mid+1,right); /对又序列进行归并Union(arr,left,mid,right); /将两个有序序列合并成一个有序的序列/一次快速排序int Partition(int arr,int left,int right )int i=left; /作为划分中的枢纽值int j=right; /右边界int temp=0; /交换时的临时变量dodo i+; /扫描左侧，当当前位置值大于枢纽值时停止while (arriarrleft);if(ij)
