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

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

2、数据随机生成；2、数组中的数据已经是非递减有序。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序#in clude#in clude#in clude#in clude/using n amespace std;void BubbleSort(i nt arr,i nt n);void QuickSort(int arr,int left,int right);void SelectSort(int arr,int n);void Union Sort(i nt arr,i nt left,i nt right)

3、; int Partiti on (i nt arr,i nt left,i nt right);void Union (i nt arr,i nt left,i nt mid,i nt right); con st int ARRAY_MAXSIZE=10000; / int main (i nt argc,char *argv)/int array_SortARRAY_MAXSIZE; / int array_Sort2ARRAY_MAXSIZE; for(i nt i=O;i=ARRAY_MAXSIZE;i+) / array_Sorti=ra nd()%500;for(i nt j=O

4、;jARRAY_MAXSIZE;j+) / array_Sort2j=j; clock_t start,e nd;/start=clock();/BubbleSort(array_Sort,ARRAY_MAXSIZE); en d=clock();/cout随机数组起泡排序测试耗时为： cout(double)(e nd-start) mse ndl;start=clock(); QuickSort(array_Sort,0,ARRAY_MAXSIZE-1); en d=clock();cout随机数组快速排序测试耗时为：;cout(double)(e nd-start) mse ndl;st

5、art=clock(); SelectSort(array_Sort,ARRAY_MAXSIZE); en d=clock();cout随机数组选择排序测试耗时为：;cout(double)(e nd-start) mse ndl;start=clock();Union Sort(array_Sort,0,ARRAY_MAXSIZE-1);导入时间库函数文件定义数组最大长度测试调用的排序算法耗时声明待排序的数组生成随机数组，大小为10000生成非递减数组，大小均为10000声明开始和结束的时间计数器 排序开始时间计数器/起泡排序算法测试排序结束时间计数器/快速排序算法测试/选择排序算法测试/归

6、并排序算法测试en d=clock();cout随机数组归并排序测试耗时为：;cout(double)(e nd-start) mse ndl;coute ndl;start=clock();BubbleSort(array_Sort,ARRAY_MAXSIZE);en d=clock();cout非递减数组起泡排序测试耗时为： cout(double)(e nd-start) mse ndl;start=clock();QuickSort(array_Sort,0,ARRAY_MAXSIZE-1); en d=clock();cout非递减数组快速排序测试耗时为：cout(double)(e

7、 nd-start) mse ndl;start=clock();SelectSort(array_Sort,ARRAY_MAXSIZE);en d=clock();cout非递减数组用选择排序测试耗时为：cout(double)(e nd-start) mse ndl;start=clock();Union Sort(array_Sort,0,ARRAY_MAXSIZE-1); en d=clock();cout非递减数组用归并排序测试耗时为：cout(double)(e nd-start) mse ndl;system(pause);return 0;/起泡排序的定义，需要两个参数待排数组

8、和数组长度void BubbleSort(i nt arr,i nt n)记录本次交换的位置每次待排序的到的位置临时变量存储交换时的一个值判断最近两个并做交换int excha nge=n;/int boun d=0;/int temp=0;/while(excha nge)bound=exchange;exchange=0;for(i nt i=0;iarri+1) / temp=arri;递归结束进行一次划分递归对划分后的左侧快速排序 递归对划分后的又侧快速排序int in dex=0;/int temp=0;/for(int i=0;in;i+)in dex=i;/for(i nt j=

9、i+1;j=n ;j+) if(arrjarri ndex) in dex=j; if(in dex!=i)/temp=arri; arri=arri ndex; arri ndex=temp;arri=arri+1;arri+1=temp;excha nge=i; /for循环结束时记录的是本趟循环最后交换的位置/快速排序的定义，需要三个参数待排序数组、数组左边界和右边界void QuickSort(int arr,int left,int right)if(leftright)/int pivot=Partition(arr,left,right); /QuickSort(arr,left

10、,pivot-1);/QuickSort(arr,pivot+1,right); /选择排序的定义，需要两个参数待排序数组和数组长度void SelectSort(int arr ,int n)记录每次比较中的较小数的位置交换时的临时变量默认每次循环时第一个为最小如果当前的最小值不是arri,则和记录位置的值交换/归并排序的定义，需要三个参数待排序数组、数组左边界和右边界void Union Sort(i nt arr,i nt left,i nt right) if(leftright)/int mid=(left+right)/2; / Union Sort(arr,left,mid);/

11、Un io nSort(arr,mid+1,right); / Union (arr,left,mid,right); /序列长度超过一，则进行自序列的划分将待排序列划分为两部分对左序列进行归并对又序列进行归并将两个有序序列合并成一个有序的序列/ 一次快速排序int Partiti on (i nt arr,i nt left,i nt right ) int i=left;/int j=right;/int temp=0;/dodo i+;/while (arriarrleft); if(ij)temp=arri;/arri=arrj;arrj=temp;while(ijarrleft=ar

12、rj;arrj=temp; return j;/归并排序合并两有序的子序列作为划分中的枢纽值右边界交换时的临时变量扫描左侧，当当前位置值大于枢纽值时停止扫描右侧，当当前位置值大于枢纽值时停止交换当前i和j记录位置的值当ij时继续do时本趟循环结束，交换枢纽值和 j位置的值void Union (i nt arr,i nt left,i nt mid,i nt right)int temp10000;/int i=left;int j=mid+1;int k=0;while(i=mid )&(j=right) / if(arri=arrj) tempk+=arri+;else tempk+=ar

13、rj+;while(i=mid) tempk+=arri+;while(j=right) tempk+=arrj+;for(i=0,k=left;k 勺,勺S .耐 In0 2rn呂56 33 2*;为为TJ -nJ 41rJfL 3 3 trxrr u,UI2, I “ I “- SI -幵 沟a选归缄 1S1 二一.二二二- 数數数書 HU =二一_二_脣 _ 二二二一一一匸日 D为8000如下数组大小 ARRAY MAXSIZEVTISVTIS plpl6 04 u 6 6C3 3 117J为为为严 _,K 二 L_,JLC*TrHlE-lrr-f一31厂 y F31厂71Ln itb-

14、47山162 : -；刿対 为为舅 B B ? *7 试、一，q.* 一 q* 诂试牧妆 劭星- si -归续 起快用暑 组组组组裡 数数数馥倉 厘理诲I-亠女 T Ta -Ta .1b_TA ?- 匚 二 - - -!冃 二一 二 T 13数组大小 ARRAY MAXSIZE 为5000如下:F：隔月云氷耒評 A stjdyMry-tr/DeougT ry_tr- ex=3fsmm 叱吕SS吟VTtssill mnlll2 701. 3 8 7 1 Jr_nJ 丄!: |4 为为朋朋 頁为为为 丄二* _ 1-二 JLLJ 丄 i I . I 云fiBkJB试试顒液 毎轉劭传- 泡违择斗起快

15、用用理 快选归组组组營 姐纽组组数数数觀音 - 数数芻Utt mm机机 递递递礬 3E运.J_.-n七、 实验分析1、各算法时间时间消耗图2、各算法时间性能分析表:方法最好情况最坏情况平均情况起泡排序O(n)O(n2 )O(n2 )快速排序O(nl og2 n)O(n2 )O(nl og2 n)选择排序O(n2 )O(n2 )O(n2 )归并排序O(nl og2 n)O(nl og2 n)O(nl og2 n)3、分析与说明:由算法时间复杂度表分析，起泡排序在最好情况下时间性能好， 最坏情况和平均情况和选择排序一样，选择排序的时间性能都不高， 均为0(n2 ),根据平均情况来看，快速排序和归并排序的时间性能一 样，且最坏情况时归并排序优于快速排序。对于随机数组序列，数组大小为 10000, 8000, 5