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

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

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

3、序完成題目要求main/產生隨即數(shù)randomnumberbeforesort=randomnumber/根據(jù)題目要求計算所需時間并比較cost1=./ timecost(int beforesort, int mode)cost2=.cost3=./運行時間計算double timecost(int beforesort, int mode)記住系統(tǒng)時間 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)時間 current1cost = (current1-current0)/n;return cost;/排序算法，任意找三種sort1(int beforesort)/algorithm1sort2(int beforesort)/algorithm2sort3(int beforesort)/algorithm3代碼完成 第一步：測試隨即數(shù)函數(shù)是否正確，隨機數(shù)產生由函數(shù)srand(unsigned)time( null ) )實現(xiàn)，在這代碼后添加顯示函數(shù)printf(thousand random numbers from 0 to 20

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

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

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

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

9、素結點類型*/typedef structlong int cp; /*記錄比較次數(shù)*/long int mv; /*記錄移動次數(shù)*/cpmv;/*r為待排序列的數(shù)組*/*n為待排序列元素的個數(shù)*/*cm用于記錄關鍵字的比較和移動次數(shù)*/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+;/*比較一次，比較次數(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; /*關鍵字移動次數(shù)加3*/cm-cp+; /*執(zhí)行if語句，比較次數(shù)加1*/j-;/*如果無記錄交換發(fā)生，則退出循環(huán)*/ count+; return count;/*s為排序區(qū)間的起始點*/*t為排序區(qū)間的終止點*/void quicksort(recdtype r,int s,int t,cpmv * cm) /*快速排序*/int low=

11、s;int high=t;r0=rs; /*將基準記錄移至r0中*/while(lowhigh)while(lowhigh & r0.keycp+; /*循環(huán)執(zhí)行一次，計較次數(shù)加1*/cm-cp+; /*最后一次比較，次數(shù)加1*/if(lowmv+; /*關鍵字移動次數(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移動到它的終結位置*/cm-mv+;if(s

12、low)quicksort(r,s,high-1,cm); /*對rs到rhigh-1區(qū)間進行快速排序*/if(lowt)quicksort(r,high+1,t,cm); /*對rhigh+1到rt區(qū)間進行快速排序*/void restore(recdtype r,recdtype r1,int n) /*恢復原始數(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; /程序運行所需時間 int kk

13、=100;int i=mode;clock_t start,finish;switch(i)case 1: start=clock(); /開始時間/cout以下進行插入排序: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(); /終止時間 cost=(float)(finish-start)/kk; /通過終止和起始時間計算得出運行所需時間，原始單位為秒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;) /*輸出顯示格式的設置,每行顯示14個數(shù)，共1000個數(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ù)移動次數(shù)的平均值*/ srand(unsigned)time( null ) ); /*初始化隨機發(fā)生器*/printf(thousand random numbers from 0 to 2000nn)

16、;for(i=0;in;) /*輸出顯示格式的設置,每行顯示14個數(shù)，共1000個數(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); /顯示運行時間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); /顯示運行時間printf(s);printf(bubble sort data:n);printf(compare number:%ld,move number