嵌入式linux实验报告-三种排序算法的在linux和arm上执行速度比较
嵌入式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
{ for(j=0;j<13;j++)
{ r[j+i].key=rand()%2000;
r1[i].key=r[i].key;
printf("%-6d",r[j+i].key);}
printf("\n");
i=i+13;}
以观察随机数是否正确，这里开始处理点小问题，因为本实验要用同一排序法对同一组数据进行排序，每次排序后要恢复原待排序的数组，所以定义了两个同样的数组类型recdtype r[N+1],r1[N+1]，后者用于恢复时使用。首先每产生一个随机数放到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)，当待排序数有序时，退化为冒泡排序，不稳定；
第三步：测试三种排序的正确性，单独验证其正确，放在一个单独
