嵌入式linux實(shí)驗(yàn)報(bào)告三種排序算法的在linux和arm上執(zhí)行速度比較

1、嵌入式linux設(shè)計(jì)實(shí)驗(yàn)報(bào)告 項(xiàng)目概要名稱：三種排序算法的在linux和arm上執(zhí)行速度比較具體內(nèi)容和實(shí)驗(yàn)要求：三種或三種以上排序算法在arm linux上執(zhí)行速度的比較：例如可以隨機(jī)產(chǎn)生1000個(gè)數(shù)，在排序過(guò)程開(kāi)始前計(jì)下系統(tǒng)時(shí)間，結(jié)束后再計(jì)下系統(tǒng)時(shí)間，算出時(shí)間差即為算法執(zhí)行時(shí)間，每種算法需要多重復(fù)幾次取平均值。 項(xiàng)目分工需求分析：共同完成概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)：（李春元）負(fù)責(zé)整個(gè)程序的框架設(shè)計(jì)和具體函數(shù)的實(shí)現(xiàn)即代碼注釋；調(diào)試和改進(jìn)：（李紅）代碼調(diào)試，包括調(diào)試實(shí)例的設(shè)計(jì)，功能的擴(kuò)展和補(bǔ)充；實(shí)現(xiàn)：（共同完成）從visual c+調(diào)試成功，移植到linux系統(tǒng)下的相關(guān)改進(jìn)（庫(kù)的變化等等），掛載到arm

2、9上的過(guò)程，比較三種環(huán)境下運(yùn)行時(shí)間的差異。 項(xiàng)目需求分析由實(shí)驗(yàn)要求可知，首先是確定三種排序算法，這個(gè)容易解決，我們選擇的是快速排序，冒泡排序，簡(jiǎn)單排序；接著是隨機(jī)數(shù)的產(chǎn)生；然后是怎樣計(jì)下系統(tǒng)時(shí)間，最后是怎樣用系統(tǒng)時(shí)間來(lái)計(jì)算多次排序的平均值，這里又會(huì)涉及到數(shù)據(jù)類型的強(qiáng)制轉(zhuǎn)換。所以要實(shí)現(xiàn)這些要求，包括的函數(shù)主要有：main函數(shù)，冒泡排序函數(shù)，簡(jiǎn)單排序函數(shù)，快速排序函數(shù)，排序時(shí)間計(jì)算函數(shù)。代碼的框架和具體的實(shí)驗(yàn)代碼（概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)）由李春元同學(xué)完成。 概要設(shè)計(jì)包括系統(tǒng)整體軟硬件流程圖，各個(gè)功能子模塊的劃分和描述；產(chǎn)生隨機(jī)數(shù)快速排序冒泡排序簡(jiǎn)單排序時(shí)間統(tǒng)計(jì) 調(diào)試結(jié)果與改進(jìn)方案工程框架/main主程

3、序完成題目要求main/產(chǎn)生隨即數(shù)randomnumberbeforesort=randomnumber/根據(jù)題目要求計(jì)算所需時(shí)間并比較cost1=./ timecost(int beforesort, int mode)cost2=.cost3=./運(yùn)行時(shí)間計(jì)算double timecost(int beforesort, int mode)記住系統(tǒng)時(shí)間 current0for iteration=1:n /n 為排序算法多次執(zhí)行的次數(shù)case mode=1 sort1(int beforesort)case mode=2 sort2(int beforesort)case mode=3so

4、rt3(int beforesort)end記住系統(tǒng)時(shí)間 current1cost = (current1-current0)/n;return cost;/排序算法，任意找三種sort1(int beforesort)/algorithm1sort2(int beforesort)/algorithm2sort3(int beforesort)/algorithm3代碼完成 第一步：測(cè)試隨即數(shù)函數(shù)是否正確，隨機(jī)數(shù)產(chǎn)生由函數(shù)srand(unsigned)time( null ) )實(shí)現(xiàn)，在這代碼后添加顯示函數(shù)printf(thousand random numbers from 0 to 20

5、00nn);for(i=0;in;) /*輸出顯示格式的設(shè)置,每行顯示14個(gè)數(shù)，共1000個(gè)數(shù)*/ for(j=0;j（冒泡排序，簡(jiǎn)單排序）。后兩者基本相同。 第五步：為了更好的體現(xiàn)個(gè)排序算法的優(yōu)劣，還加入了記錄移動(dòng)次數(shù)和比較次數(shù)的變量，當(dāng)待排序數(shù)很多和排序次數(shù)很大時(shí)影響也會(huì)很大，所以要驗(yàn)證移動(dòng)次數(shù)和比較次數(shù)，這個(gè)和第三步共同進(jìn)行。 第六步：在linux系統(tǒng)上運(yùn)行時(shí)要注意兩者的兼容性，開(kāi)始時(shí)李春元同學(xué)用了c+的輸出輸入流來(lái)顯示輸出，這在linux的編譯環(huán)境下是不支持的，最后都改成了c中的printf語(yǔ)句以及main函數(shù)返回值不能為void。還要注意的是文件的后綴是.c。在linux上實(shí)現(xiàn)后，掛

6、載到arm上再通過(guò)終端顯示。實(shí)驗(yàn)結(jié)果同1000個(gè)數(shù)經(jīng)100次排序后的平均數(shù)據(jù)a） window 上運(yùn)行結(jié)果：b） linux上運(yùn)行結(jié)果：運(yùn)行時(shí)間（s）數(shù)據(jù)移動(dòng)次數(shù)比較次數(shù)簡(jiǎn)單排序0.028049450500292605冒泡排序0.03004945050010838124快速排序0.019042276168218790c） （arm）終端上運(yùn)行結(jié)果：運(yùn)行時(shí)間（s）數(shù)據(jù)移動(dòng)次數(shù)比較次數(shù)簡(jiǎn)單排序10.460049450500292605冒泡排序12.15004945050010838124快速排序7.330042276539218741存在的問(wèn)題和改進(jìn)的方法； 程序中并沒(méi)有涉及到判斷排序是否是穩(wěn)定的

7、，這是需要改進(jìn)的地方，這在前面也提到了，在設(shè)計(jì)結(jié)構(gòu)體typedef struct keytype key; /*定義關(guān)鍵字類型*/elemtype data; /*定義元素中其他數(shù)據(jù)項(xiàng)*/recdtype; /*定義元素結(jié)點(diǎn)類型*/想到了這點(diǎn)，但沒(méi)有深入下去，其實(shí)到這里也算是做到了，只需在初始化時(shí)對(duì)data賦初始值，標(biāo)記每個(gè)數(shù)據(jù)的位置，移動(dòng)時(shí)整個(gè)節(jié)點(diǎn)一起移動(dòng)，最后每個(gè)節(jié)點(diǎn)完整輸出，看key相同但data值不同的節(jié)點(diǎn)相對(duì)位置是變化了，沒(méi)變則是穩(wěn)定的，反之不穩(wěn)定。參考文獻(xiàn)【1】數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版） 嚴(yán)蔚敏 吳偉明 編著，清華大學(xué)出版社；【2】c語(yǔ)言程序設(shè)計(jì) 譚浩強(qiáng) 著 清華大學(xué)出版社；【3】嵌入式

8、設(shè)計(jì)及l(fā)inux驅(qū)動(dòng)開(kāi)發(fā)指南基于arm 9處理器 孫天澤，袁文菊，張海峰，北京：電子工業(yè)出版社；【4】 嵌入式linux應(yīng)用開(kāi)發(fā)詳解孫瓊等 北京：人民郵電出版社；源代碼#include #include #include const int n=1000; /*待排序的數(shù)據(jù)個(gè)數(shù)常量*/typedef int keytype; /*關(guān)鍵字?jǐn)?shù)據(jù)類型定義*/typedef int elemtype;/*元素節(jié)點(diǎn)其他數(shù)據(jù)項(xiàng)數(shù)據(jù)類型定義*/typedef struct keytype key; /*定義關(guān)鍵字類型*/elemtype data; /*定義元素中其他數(shù)據(jù)項(xiàng)*/recdtype; /*定義元

9、素結(jié)點(diǎn)類型*/typedef structlong int cp; /*記錄比較次數(shù)*/long int mv; /*記錄移動(dòng)次數(shù)*/cpmv;/*r為待排序列的數(shù)組*/*n為待排序列元素的個(gè)數(shù)*/*cm用于記錄關(guān)鍵字的比較和移動(dòng)次數(shù)*/void simplesort(recdtype r,int n,cpmv * cm) /*簡(jiǎn)單選擇排序法:由小到大排列*/ int i,j,k; recdtype t; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(rj.keycp+;/*比較一次，比較次數(shù)加一*/ if(k!=i) t=ri;ri=rk;rk=t; c

10、m-mv+=3;/*交換次數(shù)加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; /*關(guān)鍵字移動(dòng)次數(shù)加3*/cm-cp+; /*執(zhí)行if語(yǔ)句，比較次數(shù)加1*/j-;/*如果無(wú)記錄交換發(fā)生，則退出循環(huán)*/ count+; return count;/*s為排序區(qū)間的起始點(diǎn)*/*t為排序區(qū)間的終止點(diǎn)*/void quicksort(recdtype r,int s,int t,cpmv * cm) /*快速排序*/int low=

11、s;int high=t;r0=rs; /*將基準(zhǔn)記錄移至r0中*/while(lowhigh)while(lowhigh & r0.keycp+; /*循環(huán)執(zhí)行一次，計(jì)較次數(shù)加1*/cm-cp+; /*最后一次比較，次數(shù)加1*/if(lowmv+; /*關(guān)鍵字移動(dòng)次數(shù)加1*/low+;while(lowhigh & rlow.keycp+; /*循環(huán)執(zhí)行一次，比較次數(shù)加1*/if(low!=high) cm-cp+; /*比較次數(shù)加1*/if(lowmv+;high-; /*high指針繼續(xù)向前搜索*/rlow=r0; /*low=high，將r0移動(dòng)到它的終結(jié)位置*/cm-mv+;if(s

12、low)quicksort(r,s,high-1,cm); /*對(duì)rs到rhigh-1區(qū)間進(jìn)行快速排序*/if(lowt)quicksort(r,high+1,t,cm); /*對(duì)rhigh+1到rt區(qū)間進(jìn)行快速排序*/void restore(recdtype r,recdtype r1,int n) /*恢復(fù)原始數(shù)據(jù),用于每次排序后*/int i;for(i=1;i=n;i+)ri=r1i;.float timecost(recdtype* r,recdtype* r1,int n,cpmv* cm,int mode)int k=0;float cost; /程序運(yùn)行所需時(shí)間 int kk

13、=100;int i=mode;clock_t start,finish;switch(i)case 1: start=clock(); /開(kāi)始時(shí)間/cout以下進(jìn)行插入排序:endl;/coutendl;for(k=1;kkk;k+) simplesort(r,n,cm);restore(r,r1,n);finish=clock(); /cost=(float)(finish-start)/kk;break;case 2:start=clock(); int count;for(k=1;kkk;k+)count=bubblesort(r,n,cm);restore(r,r1,n);finis

14、h=clock(); cost=(float)(finish-start)/kk; break;case 3:start=clock(); for(k=1;kkk;k+)quicksort(r,1,n,cm);restore(r,r1,n);finish=clock(); /終止時(shí)間 cost=(float)(finish-start)/kk; /通過(guò)終止和起始時(shí)間計(jì)算得出運(yùn)行所需時(shí)間，原始單位為秒break;default:printf(* ); return cost;int main()int i,j;float cost;printf(thousand random numbers f

15、rom 0 to 2000nn);for(i=0;in;) /*輸出顯示格式的設(shè)置,每行顯示14個(gè)數(shù)，共1000個(gè)數(shù)*/ for(j=0;j13;j+) rj+i.key=rand()%2000; r1i.key=ri.key; printf(%-6d,rj+i.key);printf(n);i=i+13; cpmv cm3;cpmv * p;/*cmpv類型指針,中間變量,記錄排序的比較次數(shù)移動(dòng)次數(shù)的平均值*/ srand(unsigned)time( null ) ); /*初始化隨機(jī)發(fā)生器*/printf(thousand random numbers from 0 to 2000nn)

16、;for(i=0;in;) /*輸出顯示格式的設(shè)置,每行顯示14個(gè)數(shù)，共1000個(gè)數(shù)*/ for(j=0;j13;j+) rj+i.key=rand()%2000; r1i.key=ri.key; printf(%-6d,rj+i.key);printf(n);i=i+13;for(i=0;i3;i+) cmi.cp=0;cmi.mv=0;p=cm;printf(simple sort cost:);cost = timecost(r,r1,n,p,1)/10000;printf(%f,cost); /顯示運(yùn)行時(shí)間printf(s); printf(simple sort data:n);printf(compare number:%ld,move number:%ldn,cm0.cp,cm0.mv);restore(r,r1,n); printf(n);p+;printf(bubble sort cost:);cost = timecost(r,r1,n,p,2)/10000;printf(%f,cost); /顯示運(yùn)行時(shí)間printf(s);printf(bubble sort data:n);printf(compare number:%ld,move number