嵌入式linux设计实验报告 项目概要名称：三种排序算法的在linux和arm上执行速度比较具体内容和实验要求：三种或三种以上排序算法在ARM Linux上执行速度的比较：例如可以随机产生1000个数，在排序过程开始前计下系统时间，结束后再计下系统时间，算出时间差即为算法执行时间，每种算法需要多重复几次取平均值。 项目分工需求分析：共同完成概要设计和详细设计：（李春元）负责整个程序的框架设计和具体函数的实现即代码注释；调试和改进：（李红）代码调试，包括调试实例的设计，功能的扩展和补充；实现：（共同完成）从visual c+调试成功，移植到linux系统下的相关改进（库的变化等等），挂载到arm9上的过程，比较三种环境下运行时间的差异。 项目需求分析由实验要求可知，首先是确定三种排序算法，这个容易解决，我们选择的是快速排序，冒泡排序，简单排序；接着是随机数的产生；然后是怎样计下系统时间，最后是怎样用系统时间来计算多次排序的平均值，这里又会涉及到数据类型的强制转换。所以要实现这些要求，包括的函数主要有：main函数，冒泡排序函数，简单排序函数，快速排序函数，排序时间计算函数。代码的框架和具体的实验代码（概要设计和详细设计）由李春元同学完成。 概要设计包括系统整体软硬件流程图，各个功能子模块的划分和描述；产生随机数快速排序冒泡排序简单排序时间统计 调试结果与改进方案工程框架/main主程序完成题目要求main/产生随即数randomnumberbeforesort=randomnumber/根据题目要求计算所需时间并比较cost1=./ TimeCost(int beforesort, int mode)cost2=.cost3=./运行时间计算double TimeCost(int beforesort, int mode)记住系统时间 Current0for iteration=1:N /N 为排序算法多次执行的次数case mode=1 sort1(int beforesort)case mode=2 sort2(int beforesort)case mode=3sort3(int beforesort)end记住系统时间 Current1cost = (Current1-Current0)/N;return cost;/排序算法，任意找三种sort1(int beforesort)/algorithm1sort2(int beforesort)/algorithm2sort3(int beforesort)/algorithm3代码完成 第一步：测试随即数函数是否正确，随机数产生由函数srand(unsigned)time( NULL ) )实现，在这代码后添加显示函数printf(thousand random numbers from 0 to 2000nn);for(i=0;iN;) /*输出显示格式的设置,每行显示14个数，共1000个数*/ for(j=0;j（冒泡排序，简单排序）。后两者基本相同。 第五步：为了更好的体现个排序算法的优劣，还加入了记录移动次数和比较次数的变量，当待排序数很多和排序次数很大时影响也会很大，所以要验证移动次数和比较次数，这个和第三步共同进行。 第六步：在linux系统上运行时要注意两者的兼容性，开始时李春元同学用了c+的输出输入流来显示输出，这在linux的编译环境下是不支持的，最后都改成了c中的printf语句以及main函数返回值不能为void。还要注意的是文件的后缀是.c。在linux上实现后，挂载到arm上再通过终端显示。实验结果同1000个数经100次排序后的平均数据A） Window 上运行结果：B） Linux上运行结果：运行时间（s）数据移动次数比较次数简单排序0.028049450500292605冒泡排序0.03004945050010838124快速排序0.019042276168218790C） （arm）终端上运行结果：运行时间（s）数据移动次数比较次数简单排序10.460049450500292605冒泡排序12.15004945050010838124快速排序7.330042276539218741存在的问题和改进的方法； 程序中并没有涉及到判断排序是否是稳定的，这是需要改进的地方，这在前面也提到了，在设计结构体typedef struct keytype key; /*定义关键字类型*/elemtype data; /*定义元素中其他数据项*/recdtype; /*定义元素结点类型*/想到了这点，但没有深入下去，其实到这里也算是做到了，只需在初始化时对data赋初始值，标记每个数据的位置，移动时整个节点一起移动，最后每个节点完整输出，看key相同但data值不同的节点相对位置是变化了，没变则是稳定的，反之不稳定。参考文献【1】数据结构（C语言版） 严蔚敏 吴伟明 编著，清华大学出版社；【2】C语言程序设计 谭浩强 著 清华大学出版社；【3】嵌入式设计及Linux驱动开发指南基于ARM 9处理器 孙天泽，袁文菊，张海峰，北京：电子工业出版社；【4】 嵌入式linux应用开发详解孙琼等 北京：人民邮电出版社；源代码#include #include #include const int N=1000; /*待排序的数据个数常量*/typedef int keytype; /*关键字数据类型定义*/typedef int elemtype;/*元素节点其他数据项数据类型定义*/typedef struct keytype key; /*定义关键字类型*/elemtype data; /*定义元素中其他数据项*/recdtype; /*定义元素结点类型*/typedef structlong int cp; /*记录比较次数*/long int mv; /*记录移动次数*/cpmv;/*r为待排序列的数组*/*n为待排序列元素的个数*/*cm用于记录关键字的比较和移动次数*/void simplesort(recdtype r,int n,cpmv * cm) /*简单选择排序法:由小到大排列*/ int i,j,k; recdtype t; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(rj.keycp+;/*比较一次，比较次数加一*/ if(k!=i) t=ri;ri=rk;rk=t; cm-mv+=3;/*交换次数加3*/ int BubbleSort(recdtype r,int n,cpmv * cm) /*冒泡排序*/int i,j,count=0;int flag; for(i=1;i=i+1)if(rj.keymv+=3; /*关键字移动次数加3*/cm-cp+; /*执行if语句，比较次数加1*/j-;/*如果无记录交换发生，则退出循环*/ count+; return count;/*s为排序区间的起始点*/*t为排序区间的终止点*/void QuickSort(recdtype r,int s,int t,cpmv * cm) /*快速排序*/int low=s;int high=t;r0=rs; /*将基准记录移至r0中*/while(lowhigh)while(lowhigh & r0.keyrhigh.key )