嵌入式linux实验报告-三种排序算法的在linux和arm上执行速度比较.doc

嵌入式linux设计实验报告• 项目概要名称：三种排序算法的在linux和arm上执行速度比较具体内容和实验要求：三种或三种以上排序算法在ARM Linux上执行速度的比较：例如可以随机产生1000个数，在排序过程开始前计下系统时间，结束后再计下系统时间，算出时间差即为算法执行时间，每种算法需要多重复几次取平均值• 项目分工需求分析：共同完成概要设计和详细设计：（李春元）负责整个程序的框架设计和具体函数的实现即代码注释；调试和改进：（李红）代码调试，包括调试实例的设计，功能的扩展和补充；实现：（共同完成）从visual c++调试成功，移植到linux系统下的相关改进（库的变化等等），挂载到arm9上的过程，比较三种环境下运行时间的差异• 项目需求分析由实验要求可知，首先是确定三种排序算法，这个容易解决，我们选择的是快速排序，冒泡排序，简单排序；接着是随机数的产生；然后是怎样计下系统时间，最后是怎样用系统时间来计算多次排序的平均值，这里又会涉及到数据类型的强制转换所以要实现这些要求，包括的函数主要有：main函数，冒泡排序函数，简单排序函数，快速排序函数，排序时间计算函数代码的框架和具体的实验代码（概要设计和详细设计）由李春元同学完成。

• 概要设计包括系统整体软硬件流程图，各个功能子模块的划分和描述；产生随机数快速排序冒泡排序简单排序时间统计• 调试结果与改进方案工程框架//main主程序完成题目要求main{ //产生随即数randomnumber beforesort=randomnumber //根据题目要求计算所需时间并比较 cost1=... // TimeCost(int[] beforesort, int mode) cost2=... cost3=...}//运行时间计算double TimeCost(int[] beforesort, int mode){ 记住系统时间 Current0 for iteration=1:N //N 为排序算法多次执行的次数 case mode==1 sort1(int[] beforesort) case mode==2 sort2(int[] beforesort) case mode==3 sort3(int[] beforesort) end 记住系统时间 Current1 cost = (Current1-Current0)/N; return cost;}//排序算法，任意找三种sort1(int[] beforesort){ //algorithm1}sort2(int[] beforesort){ //algorithm2}sort3(int[] beforesort){ //algorithm3}代码完成 第一步：测试随即数函数是否正确，随机数产生由函数srand((unsigned)time( NULL ) )实现，在这代码后添加显示函数printf("thousand random numbers from 0 to 2000\n\n"); for(i=0;i

首先每产生一个随机数放到r和rl中，开始忘了这点，并没有r1[i].key=r[i].key;这句，结果排序时间均为零（太小了）第二步：分析各排序算法的时间复杂度，用于验证程序是否正确 简单排序：根据循环体计算其时间复杂度--- n(n-1)/2 O(n2)，移动次数和比较次数依具体待排数而定，空间复杂度O(1)，不稳定； 冒泡排序：根据循环体计算其时间复杂度--- n(n-1)/2 O(n2)，移动次数和比较次数依具体待排数而定，空间复杂度O(1)，稳定；快速排序：根据循环体计算其时间复杂度--- O(nlogn)，移动次数和比较次数依具体待排数而定，空间复杂度O(logn)，当待排序数有序时，退化为冒泡排序，不稳定；第三步：测试三种排序的正确性，单独验证其正确，放在一个单独的程序中验证，只是验证一次排序的移动次数和比较次数，以及排序的的稳定性，测试的数据换成只有十个比较简单的数（0到20），这里就体现出了为什么李春元同学为什么要用一个结构体来表示每个数据，结构体中既包含了关键字的大小，也包括了每个关键字的位置信息，便于判断排序算法是否稳定，但是实验中并没有体现这点，这是考虑到了这个可能。

这部分比较简单，没出大问题 第四步：对计算运行时间的函数的验证和整个程序的验证是一起进行的，总要是通过看三种排序所花的平均时间的大小来判断程序是否正确预计的是快速排序>（冒泡排序，简单排序）后两者基本相同 第五步：为了更好的体现个排序算法的优劣，还加入了记录移动次数和比较次数的变量，当待排序数很多和排序次数很大时影响也会很大，所以要验证移动次数和比较次数，这个和第三步共同进行 第六步：在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 struct{ long 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;icp++;/*比较一次，比较次数加一*/ } if(k!=i) { t=r[i];r[i]=r[k];r[k]=t; cm->mv+=3;/*交换次数加3*/ } }}int BubbleSort(recdtype r[],int n,cpmv * cm) /*冒泡排序*/{ int i,j,count=0; int flag; for(i=1;i<=n-1;i++) { flag=0; j=n; while(j>=i+1) { if(r[j].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; r[0]=r[s]; /*将基准记录移至r[0]中*/ while(low