嵌入式linux实验报告-通信0701-李春元

《嵌入式linux实验报告-通信0701-李春元》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、嵌入式linux设计实验报告组号：5姓名：李春元学号：U200713569同组同学：李红专业班级：通信0701指导老师：鄢舒•项目概要名称：三种排序算法的在linux和arm上执行速度比较具体内容和实验要求：三种或三种以上排序算法在ARMLinux上执行速度的比较：例如可以随机产生1000个数，在排序过程开始前计下系统时间，结束后再计下系统时间，算出时间差即为算法执行时间，每种算法需要多重复几次取平均值。•项目分工需求分析：共同完成概要设计和详细设计：（李春元）负责整个程序的框架设计和具体函数的实现即代码注释；调试和改进：（李红）代码调试，包括调试实例的设计，功能的扩展和补充；实现：（共

2、同完成）从visualc++调试成功，移植到linux系统下的相关改进（库的变化等等），挂载到arm9上的过程，比较三种环境下运行时间的差异。•项目需求分析由实验要求可知，首先是确定三种排序算法，这个容易解决，我们选择的是快速排序，冒泡排序，简单排序；接着是随机数的产生；然后是怎样计下系统时间，最后是怎样用系统时间来计算多次排序的平均值，这里又会涉及到数据类型的强制转换。所以要实现这些要求，包括的函数主要有：main函数，冒泡排序函数，简单排序函数，快速排序函数，排序时间计算函数。代码的框架和具体的实验代码（概要设计和详细设计）由李春元同学完成。•概要设计包括系统整体软硬件流程图，各个功

3、能子模块的划分和描述；产生随机数快速排序冒泡排序简单排序时间统计•调试结果与改进方案工程框架//main主程序完成题目要求main{//产生随即数randomnumberbeforesort=randomnumber//根据题目要求计算所需时间并比较cost1=...//TimeCost(int[]beforesort,intmode)cost2=...cost3=...}//运行时间计算doubleTimeCost(int[]beforesort,intmode){记住系统时间Current0foriteration=1:N//N为排序算法多次执行的次数casemode==1sort1

4、(int[]beforesort)casemode==2sort2(int[]beforesort)casemode==3sort3(int[]beforesort)end记住系统时间Current1cost=(Current1-Current0)/N;returncost;}//排序算法，任意找三种sort1(int[]beforesort){//algorithm1}sort2(int[]beforesort){//algorithm2}sort3(int[]beforesort){//algorithm3}代码完成第一步：测试随即数函数是否正确，随机数产生由函数srand((uns

5、igned)time(NULL))实现，在这代码后添加显示函数printf("thousandrandomnumbersfrom0to2000");for(i=0;i

6、个同样的数组类型recdtyper[N+1],r1[N+1]，后者用于恢复时使用。首先每产生一个随机数放到r和rl中，开始忘了这点，并没有r1[i].key=r[i].key;这句，结果排序时间均为零（太小了）。第二步：分析各排序算法的时间复杂度，用于验证程序是否正确。简单排序：根据循环体计算其时间复杂度---n(n-1)/2O(n2)，移动次数和比较次数依具体待排数而定，空间复杂度O(1)，不稳定；冒泡排序：根据循环体计算其时间复杂度---n(n-1)/2O(n2)，移动次数和比较次数依具体待排数而定，空间复杂度O(1)，稳定；快速排序：根据循环体计算其时间复杂度---O(nlogn)

7、，移动次数和比较次数依具体待排数而定，空间复杂度O(logn)，当待排序数有序时，退化为冒泡排序，不稳定；第三步：测试三种排序的正确性，单独验证其正确，放在一个单独的程序中验证，只是验证一次排序的移动次数和比较次数，以及排序的的稳定性，测试的数据换成只有十个比较简单的数（0到20），这里就体现出了为什么李春元同学为什么要用一个结构体来表示每个数据，结构体中既包含了关键字的大小，也包括了每个关键字的位置信息，便于判断排序算法是否稳定，