下载文档原格式
实验报告题目实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。
二、实验内容设计一个递归和分治算法，找出数组的最大元素，找出x在数组A中出现的次数。
三、实验要求（1）用分治法求解…问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1.设计一个递归算法，找出数组的最大元素。
2.设计一个分治算法，找出x在数组A中出现的次数。
3.写一个主函数，调用上述算法。
五、实验结果分析（分析时空复杂性，设计测试用例及测试结果）时间复杂性：最好情况下，O(n)最坏情况下：O(nlog(n)空间复杂性分析：O(n)六、实验体会通过写递归与分治策略实验，更加清楚的知道它的运行机理，分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
做实验重在动手动脑，还是要多写写实验，才是硬道理。
七、附录：（源代码）#include"stdio.h"#define ElemType intint count(ElemType a[],int i,int j,ElemType x){int k=0,mid; //k用来计数，记录数组中x出现的次数if(i==j){if(a[i]==x) k++;return k;}else{mid=(i+j)/2;k+=count(a,i,mid,x);k+=count(a,mid+1,j,x);}return k;}ElemType Maxitem(ElemType a[],int n){ElemType max=a[n-1],j;if(n==1){max=a[n-1];return max;}else{j=Maxitem(a,n-1);if(j>max) max=j;return max;}}void main(void){ElemType a[]={1,5,2,7,3,7,4,8,9,5,4,544,2,4,123};ElemType b;ElemType x;int n;b=Maxitem(a,15);printf("数组的最大元素为%d\n",b);printf("输入想要计数的数组元素:\n");scanf("%d",&x);n=count(a,0,14,x);printf("%d在数组中出现的次数为%d次\n",x,n);}实验二动态规划——求解最优问题一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。
算法分析设计与实验王 源二0一四年十月实验一：分治算法及其应用实验要求：掌握分治算法的原理.掌握递归算法及递归程序的设计.能用程序设计语言设计求解典型问题的算法实验题：1、棋盘覆盖问题：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。
2、最近对问题：设p 1=(x 1,y 1), p 2=(x 2,y 2), …, p n =(x 1,y 1)，是平面上n 个点构成的集合S ，最近对问题就是找出集合S 中距离最近的点对。
3、（选作）最大子段和问题：给定由n 个整数（可能有负整数）组成的序列(a 1, a 2, …, a n )，最大子段和问题要求该序列形如 的最大值（1≤i ≤j ≤n ），当序列中所有整数均为负整数时，其最大子段和为0。
例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为 。
∑=ji k k a ∑==4220k k a实验要求：基本动态规划法的原理方法；能用程序设计语言实现求解背包问题的算法实验题：1、最长公共子序列问题：对给定序列X=(x1, x2,…, xm)和序列Z=(z1, z2,…, zk)，Z是X的子序列当且仅当存在一个递增下标序列(i1, i2,…, ik)，使得对于所有j=1, 2, …, k，有（1≤ij ≤m）。
给定两个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列最长公共子序列问题就是在序列X和Y中查找最长的公共子序列。
2、（选作）多段图的最短路径问题：设图G=(V, E)是一个带权有向图，如果把顶点集合V 划分成k个互不相交的子集Vi (2≤k≤n, 1≤i≤k)，使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+m (1≤i≤k, 1＜i+m≤k)，则称图G为多段图，称s∈V1为源点，t∈Vk为终点。
算法设计与分析实验报告一实验名称统计数字问题评分实验日期2014 年11 月15 日指导教师姓名专业班级学号一.实验要求1、掌握算法的计算复杂性概念。
2、掌握算法渐近复杂性的数学表述。
3、掌握用C++语言描述算法的方法。
4．实现具体的编程与上机实验，验证算法的时间复杂性函数。
二.实验内容统计数字问题1、问题描述一本书的页码从自然数1 开始顺序编码直到自然数n。
书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。
例如，第6 页用数字6 表示，而不是06 或006 等。
数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9)2、编程任务给定表示书的总页码的10 进制整数n (1≤n≤109) 。
编程计算书的全部页码中分别用到多少次数字0，1，2， (9)三.程序算法将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。
把这些结果统计起来即可。
四.程序代码#include<iostream.h>int s[10]; //记录0~9出现的次数int a[10]; //a[i]记录n位数的规律void sum(int n,int l,int m){ if(m==1){int zero=1;for(int i=0;i<=l;i++) //去除前缀0{ s[0]-=zero;zero*=10;} }if(n<10){for(int i=0;i<=n;i++){ s[i]+=1; }return;}//位数为1位时,出现次数加1//位数大于1时的出现次数for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1){m=1;int i;for(i=1;i<t;i++)m=m*10;a[t]=t*m;}int zero=1;for(int i=0;i<l;i++){ zero*= 10;} //求出输入数为10的n次方int yushu=n%zero; //求出最高位以后的数int zuigao=n/zero; //求出最高位zuigaofor(i=0;i<zuigao;i++){ s[i]+=zero;} //求出0~zuigao-1位的数的出现次数for(i=0;i<10;i++){ s[i]+=zuigao*a[l];} //求出与余数位数相同的0~zuigao-1位中0~9出现的次数//如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数if(yushu==0) //补上所缺的0数,并且最高位加1{ s[zuigao]++;s[0]+=l; }else{ i=0;while((zero/=10)>yushu){ i++; }s[0]+=i*(yushu+1);//补回因作模操作丢失的0s[zuigao]+=(yushu+1);//补回最高位丢失的数目sum(yushu,l-i-1,m+1);//处理余位数}}void main(){ int i,m,n,N,l;cout<<"输入数字要查询的数字:";cin>>N;cout<<'\n';n = N;for(i=0;n>=10;i++){ n/=10; } //求出N的位数n-1l=i;sum(N,l,1);for(i=0; i<10;i++){ cout<< "数字"<<i<<"出现了:"<<s[i]<<"次"<<'\n'; }}五.程序调试中的问题调试过程，页码出现报错。
实验一排序算法设计一、实验内容冒泡排序二、实验问题分析该问题主要涉及到了指针和循环和相互比较的方法，是综合知识的应用。
三、数学模型根据题目要求，依次对每个数据进行比较，直至得出最后结果。
如果a>b则交换位置，如果a<b则不交换。
四、程序流程图五、源代码#include <stdio.h>void sort(int a[]){int temp;for(int i=0;i<9;i++){for(int j=0;j<10-i-1;j++){if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}printf("排序后的数据\n"); for(i=0;i<10;i++){if(i==5){printf("\n");}printf("%d ",a[i]);}printf("\n");}void main(){int a[10];for(int i=0;i<10;i++){scanf("%d",&a[i]);}printf("排序前的数据\n"); for(i=0;i<10;i++){if(i==5){printf("\n");}printf("%d ",a[i]);}printf("\n");sort(a);}六、测试结果实验二递归算法设计一、实验内容1.判断S字符是否为“回文”的递归函数，并编写程序测试。
二、实验问题分析递归是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。
递归算法设计，就是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题，在逐步求解小问题后，再返回（回溯）得到大问题的解。
《算法设计与分析》实验指导《算法分析与设计》实验指导 .1 实验一锦标赛问题 [实验目的] 1. 基本掌握分治算法的原理. 2. 能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1. 认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2. 设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有 n=2 k 个运动员要进行网球循环赛。
现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他 n-1 个选手各赛一次；（2）每个选手一天只能参赛一次；（3）循环赛在 n-1 天内结束。
请按此要求将比赛日程表设计成有 n 行和 n-1 列的一个表。
在表中的第 i 行，第 j 列处填入第 i 个选手在第 j 天所遇到的选手。
其中 1≤i≤n，1≤j≤n-1。
[实验提示] 我们可以按分治策略将所有的选手分为两半，则 n 个选手的比赛日程表可以通过 n/2个选手的比赛日程表来决定。
递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
这时只要让这两个选手进行比赛就可以了。
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 6 7 8 5 3 4 1 2 7 8 5 6 1 2 3 4 3 2 1 8 5 6 7 1 2 3 4 5 6 7 8 1 4 3 2 1 2 1 4 3 6 5 8 7 2 1 4 3 1 2 3 4 1 2 7 8 5 6 3 2 1 4 2 1 4 3 2 1 8 7 6 5 4 3 2 1 （1）（2）（3）图 1 2 个、4 个和 8 个选手的比赛日程表图 1 所列出的正方形表（3）是 8 个选手的比赛日程表。
其中左上角与左下角的两小块分别为选手 1 至选手 4 和选手 5 至选手 8 前 3 天的比赛日程。
据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这2 样我们就分别安排好了选手 1 至选手 4 和选手 5 至选手 8 在后 4 天的比赛日程。
深圳大学实验报告课程名称：算法分析与复杂性理论实验名称：实验四动态规划学院：计算机与软件学院专业：软件工程报告人：文成学号：2150230509班级：学术型同组人：无指导教师：杨烜实验时间：2015/11/5——2015/11/18实验报告提交时间：2015/11/18教务处制一． 实验目的与实验内容实验目的：（1） 掌握动态规划算法设计思想。
（2） 掌握背包问题的动态规划解法。
实验内容：1.编写背包问题的动态规划求解代码。
2．背包容量为W ，物品个数为n ，随机产生n 个物品的体积（物品的体积不可大于W ）与价值，求解该实例的最优解。
3. 分别针对以下情况求解 第一组：（n=10,W=10），（n=10,W=20），（n=10,W=30） 第二组：（n=20,W=10），（n=20,W=20），（n=20,W=30） 第三组：（n=30,W=10），（n=30,W=20），（n=30,W=30）4. 画出三组实验的时间效率的折线图，其中x 轴是W 的值，y 轴是所花费的时间，用不同的颜色表示不同n 所花费的时间。
二．实验步骤与结果背包问题的问题描述：给定n 种物品和一个背包。
物品i 的重量是i w ，其价值为i v ，背包容量为C 。
问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？背包问题的算法思想：考虑一个由前i 个物品（1<=i<=n ）定义的实例，物品的重量分别为w1，…，w2、价值分别为v1，…，vi ，背包的承重量为j （1<=j<=w ）。
设v[i,j]为该实例的最优解的物品总价值，也就是说，是能够放进承重量为j 的背包中的前i 个物品中最有价值子集的总价值。
可以把前i 个物品中能够放进承重量为j 的背包中的子集分成两个类别：包括第i 个物品的子集和不包括第i 个物品的子集。
1. 根据定义，在不包括第i 个物品的子集中，最优子集的价值是V[i-1,j]。
实验一串匹配程序设计（2学时）一、实验目的(1). 熟练掌握串匹配的含义(2). 掌握BF算法匹配的过程并编程实现(3). 熟悉C++编译环境的基本操作二、实验内容给定两个字符串S和T，用BF算法，在主串S中查找字串T，输出结果，输出时要求有文字说明。
请编写程序。
三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（匹配成功或不成功）(3)、写出完整的程序四、实验结果实验二排序问题程序设计（2学时）一、实验目的(1). 掌握选择排序和起泡排序的基本思想(2). 掌握两种排序方法的具体实现过程(3). 在掌握的基础上编程实现两种排序方法二、实验内容输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明。
请编写程序。
三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（序列本身已是有序序列，序列不是有序序列）(3)、写出完整程序四、实验结果实验三数字旋转方阵程序设计（2学时）一、实验目的(1). 掌握分治法的设计思想(2). 掌握数字旋转方阵的具体实现过程(3). 熟练掌握二维数组的使用方法(4). 在掌握的基础上编程实现数字旋转方阵的实现过程二、实验内容给出一个初始数据，在此数据的基础上由外层向里层填写数据，完成一个数字旋转方阵，输出结果，输出时要求有文字说明。
请编写程序。
三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（方阵有一层，两层或更多层）(3)、写出完整程序四、实验结果实验四排序中分治法的程序设计（2学时）一、实验目的(1). 掌握归并排序和快速排序的划分方法(2). 掌握归并排序和快速排序的具体分治策略(3). 在掌握的基础上编程两种排序方法的实现过程二、实验内容给出一个初始序列，分别用归并排序和快速排序两种分治法将所给序列变换为有序序列，输出结果，输出时要求有文字说明。
《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：122208206101姓名：蔡猛班级：网络工程日期：2013-2014学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。
1、求n个元素的全排。
（30分）算法分析：用递归的方法，先将n个数分成两个部分，然后将两个部分交换位子，然后再将这两个部分继续再分成四个部分，然后再将每个部分进行交换，然后就重复刚才的过程，直到不能再分为止，在这个过程中所产生的所有结果就是我们要求的全排列。
代码实现：#include <stdio.h>int n = 0;void swap(int *a, int *b){int m;m = *a;*a = *b;*b = m;}void perm(int list[], int k, int m){int i;if(k > 2){for(i = 0; i <= 2; i++)printf("%d ", list[i]);printf("\n");n++;}else{for(i = k; i <= 2; i++){swap(&list[k], &list[i]);perm(list, k + 1, 4);swap(&list[k], &list[i]);}}}int main(){int list[] = {1, 2, 3,4};perm(list, 0, 2);printf("total:%d\n", n);return 0;}2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。
《算法设计与分析》课程实验指导书作者：姜文君杨明李梦娴单位：信息科学与工程学院2015年4月一、实验教学目标《算法设计与分析》旨在教会学生处理各种问题的方法，而通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。
只有通过实验，学生才能判定自己所拟算法是否正确，是否算得上一个较优算法。
通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识。
同时培养学生的实际动手能力，加强学生创新思维能力的培养。
二、实验教学主要内容实验课外时间组织：实验课外消化理论课堂，老师对项目实验的讲解，并且做好相关的设计与实现。
实验课内时间组织：学生在学院机房集中上机，实验教师在机房采用辅导和自由讨论相结合的方式进行指导。
最终完成实验项目的检查。
三、实验要求《算法设计与分析》是计算机专业的专业核心课程，其先修课程有数据结构和至少一门高级语言。
算法设计与分析课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；通过此课的学习，学生应该具有针对所给的问题设计和实现高效算法的能力。
通过上机实验，将使学生熟悉、掌握课堂教学中所学的大部分算法。
同时，上机实验是对学生在软件设计方面的综合训练，包括问题分析、总体结构设计、用户界面设计（可选）、程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。
通过理论联系实际，以最终提高学生动手操作的能力以及分析问题的能力。
为了顺利完成《算法设计与分析》课程实验，学生应做到：1、熟练掌握一种高级程序设计语言及相关开发工具。
2、认真学习教材以及老师课堂讲解的项目实验相关内容，提前做好分析设计和实现。
3、自行完成代码编写，不得超袭。
实验课上课时间做好项目陈述和检查的准备，也可以针对一些问题做相应的讨论。
4、遵守机房纪律，服从辅导教师指挥，爱护实验设备。
5、实验课上进行相关的程序检查和测试，结束后提交所有的文档和源程序。
深圳大学实验报告
课程名称：算法设计与分析
实验项目名称：排序算法性能分析
学院：
专业、班级：
指导教师：杨烜
报告人：学号：
实验报告提交时间： 2015.4.3
教务处制
一、实验目的与实验环境
实验目的：
1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理
2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。
实验环境：VC++ 6.0
二、实验原理与算法描述
算法（1）选择排序 SelectSort(A[0...n-1],n)
//利用选择排序对给定的数组排序
//输入：一个可排序数组A[0...n-1]
//输出：非降序排列的数组A[0...n-1]
for i<-0 to n-2 do
min<-i
for j<-i+1 to n-1 do
if A[j]<A[min]
min<-j
swap A[i] and A[min]
理论效率：C(n) ∈θ(n^2),不稳定算法
算法（2）快速排序 QuickSort(A[0...n-1],n)
//利用快速排序对给定的数组排序
//输入：一个可排序数组A[0...n-1]
//输出：非降序排列的数组A[0...n-1]
if l<r
s<-Partition(A[l...r]) //s是分裂位置
Quicksort(A[l...s-1])
Quicksort(A[s+1...r])
Partition(A[l...r])
//以第一个数为中轴，对子数组进行分区
//输入：数组A[0...n-1]中的子数组A[l...r]，由左右下标l和r定义 //输出：数组A[l...r]的一个分区，分裂点的未知作为函数的返回值p<-A[l]
i<-l;j<-r+1
repeat
repeat i<-i+1 until A[i]>=P
repeat j<-j-1 until A[j]<=P
swap(A[i],A[j])
until i>=j
swap (A[i],A[j]) //当i>=j撤销最后一次交换
swap (A[l],A[j])
return j
理论效率：C(n) ∈θ(nlnn)，不稳定算法
算法（3）合并排序 MergeSort(A[0...n-1])
//利用合并排序对给定的数组排序
//输入：一个可排序数组A[0...n-1]
//输出：非降序排列的数组A[0...n-1]
if n>1
copy A[0...⌊n/2⌋-1] to B[0...⌊n/2⌋-1]
copy A[⌊n/2⌋...n-1] to C[0...⌈n/2⌉-1]
Mergesort(B[0...⌊n/2⌋-1])
Mergesort(C[0...⌈n/2⌉-1])
Merge(B,C,A)
Merge(B[0...p-1],C[0...q-1],A[0...p+q-1]) //将两个有序数组合并为一个有序数组
//输入：两个有序数组B[0...p-1],C[0...q-1]
//输出：A[0...p+q-1]中已经有序存放了B和C中的元素
i<-0;j<-0;k<-0
while i<p and j<q do
if B[i]<=C[j]
A[k]<-B[i];i<-i+1
else
A[k]<-C[j];j<-j+1
k<-k+1
if i=p
copy C[j...q-1] to A[k...p+q-1]
else
copy B[i...p-1] to A[k...p+q-1] 理论效率：C(n)∈θ(nlogn)，稳定算法
算法（4）冒泡排序 BubbleSort(A[0...n-1]) //利用冒泡排序对给定的数组排序
//输入：一个可排序数组A[0...n-1]
//输出：非降序排列的数组A[0...n-1]
for i<-0 to n-2 do
for j<-0 to n-2-i do
if A[j+1]<A[j]
swap A[j] and A[j+1]
理论效率：C(n)∈θ(n^2)，稳定算法
算法（5）插入排序 InsertSort(A[0...n-1],n) //利用插入排序对给定的数组排序
//输入：一个可排序数组A[0...n-1]
//输出：非降序排列的数组A[0...n-1]
for k<-2 to n do
A[0]<-A[k]
j<-k-1
while (j!=0 and A[j]>A[0]) do
A[j+1]<-A[j]
j<-j-1
A[j+1]<-A[0]
理论效率：C(n)∈θ(n^2)，稳定算法
三、实验代码与运行截图
实验关键代码：
1.选择排序
2.快速排序
3.合并排序
4.冒泡排序
5.插入排序
四、实验数据整理与分析
表一选择排序输入规模n与运行时间统计图
n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0020 0.1795 17.8550
表二快速排序输入规模n与运行时间统计图
n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0010 0.0020 0.0435
表三合并排序输入规模n与运行时间统计图
n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0005 0.0025 0.0260
表四冒泡排序输入规模n与运行时间统计图
n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0025 0.3550 39.8810
表五插入排序输入规模n与运行时间统计图
n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0005 0.0900 8.9120
图1. 选择排序时间效率与输入规模n的关系图
图2. 快速排序时间效率与输入规模n的关系图
图3. 合并排序时间效率与输入规模n的关系图
图4. 冒泡排序时间效率与输入规模n的关系图
图5. 插入排序时间效率与输入规模n的关系图
图6. 5种不同排序算法时间效率对比图
实验分析：
1.从实验结果可以看出，可以验证，当规模n趋向无穷大的时候，排序算法的效率关系为合并排序<快速排序<插入排序<选择排序<冒泡排序。
2.从实验结果可以看出，当输入规模为100000时，合并排序所需时间仅为0.026sec，而冒泡排序则大概需要40sec,合并排序的效率大概是冒泡排序的1500倍，从理论分析来看，合并排序的时间复杂度为θ(nlogn)，而冒泡排序的时间复杂度为θ(n^2),当n取100000时，两者比值大约为1500，因此可以看出，理论效率与实际效率比值基本一致。
其余几种排序算法的效率比较也和此相同。
同时，这也正是合并排序和快速排序比冒泡排序和选择排序效率高这么多的原因。
3.从算法实现的角度来看，选择排序和插入排序，都必须执行n-1趟；当冒泡排序处于最坏情况下时同样需要进行n-1趟，同时冒泡排序进行第i趟排序需要做n-i次关键字的比较和交换；而选择排序每趟执行同样要n-i-1次关键字的比较；插入排序每执行一趟排序最多比较i次；因此，这三种排序算法效率相比快速排序和合并排序较慢也是意料之中的。
4.实验测试结果与理论结果存在着差距，可能是因为测试组数较少，实验所得数据较少，因此造成数据统计以及作图不准确，造成一定的误差。
5.不同计算机的硬件系统不同，不同计算机的性能不同，因此造成不同时间测试数据的微弱差距。
五、实验结论与实验总结
实验结论：5种不同的算法都能实现排序，但效率不尽相同。
从比较可以看出，当输入规模n比较小是，各个算法的优劣体现的并不明显，当规模n达到一定程度时，不同算法之间的不同效率就明显的体现出来了。
实际效率与理论效率相比，基本一致。
可以看出，其中合并排序以及快速排序的时间效率最高。
因此，选择正确的效率高的算法，能给我们的工作带来便捷。
指导教师批阅意见：
成绩评定：
指导教师签字：
年月日备注：
注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
第11 页。
