嵌入式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ù)，在排序過程開始前計(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)（庫的變化等等），掛載到arm9上的過程，比較三種環(huán)境下運(yùn)行時(shí)間的差異? 項(xiàng)目需求分析由實(shí)驗(yàn)要求可知，首先是確定三種排序算法，這個(gè)容易解決，我們選擇的是快速排序，冒泡排序，簡單排序；接著是隨機(jī)數(shù)的產(chǎn)生；然后是怎樣計(jì)下系統(tǒng)時(shí)間，最后是怎樣用系統(tǒng)時(shí)間來計(jì)算多次排序的平均值，這里又會(huì)涉及到數(shù)據(jù)類型的強(qiáng)制轉(zhuǎn)換所以要實(shí)現(xiàn)這些要求，包括的函數(shù)主要有：main函數(shù)，冒泡排序函數(shù)，簡單排序函數(shù)，快速排序函數(shù)，排序時(shí)間計(jì)算函數(shù)代碼的框架和具體的實(shí)驗(yàn)代碼（概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)）由李春元同學(xué)完成。

? 概要設(shè)計(jì)包括系統(tǒng)整體軟硬件流程圖，各個(gè)功能子模塊的劃分和描述；產(chǎn)生隨機(jī)數(shù)快速排序冒泡排序簡單排序時(shí)間統(tǒng)計(jì)? 調(diào)試結(jié)果與改進(jìn)方案工程框架//main主程序完成題目要求main{ //產(chǎn)生隨即數(shù)randomnumber beforesort=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í)間 Current0 for iteration=1:N //N 為排序算法多次執(zhí)行的次數(shù) case mode==1 sort1(int[] beforesort) case mode==2 sort2(int[] beforesort) case mode==3 sort3(int[] beforesort) end 記住系統(tǒng)時(shí)間 Current1 cost = (Current1-Current0)/N; return cost;}//排序算法，任意找三種sort1(int[] beforesort){ //algorithm1}sort2(int[] beforesort){ //algorithm2}sort3(int[] beforesort){ //algorithm3}代碼完成 第一步：測試隨即數(shù)函數(shù)是否正確，隨機(jī)數(shù)產(chǎn)生由函數(shù)srand((unsigned)time( NULL ) )實(shí)現(xiàn)，在這代碼后添加顯示函數(shù)printf("thousand random numbers from 0 to 2000\n\n"); for(i=0;i

首先每產(chǎn)生一個(gè)隨機(jī)數(shù)放到r和rl中，開始忘了這點(diǎn)，并沒有r1[i].key=r[i].key;這句，結(jié)果排序時(shí)間均為零（太小了）第二步：分析各排序算法的時(shí)間復(fù)雜度，用于驗(yàn)證程序是否正確 簡單排序：根據(jù)循環(huán)體計(jì)算其時(shí)間復(fù)雜度--- n(n-1)/2 O(n2)，移動(dòng)次數(shù)和比較次數(shù)依具體待排數(shù)而定，空間復(fù)雜度O(1)，不穩(wěn)定； 冒泡排序：根據(jù)循環(huán)體計(jì)算其時(shí)間復(fù)雜度--- n(n-1)/2 O(n2)，移動(dòng)次數(shù)和比較次數(shù)依具體待排數(shù)而定，空間復(fù)雜度O(1)，穩(wěn)定；快速排序：根據(jù)循環(huán)體計(jì)算其時(shí)間復(fù)雜度--- O(nlogn)，移動(dòng)次數(shù)和比較次數(shù)依具體待排數(shù)而定，空間復(fù)雜度O(logn)，當(dāng)待排序數(shù)有序時(shí)，退化為冒泡排序，不穩(wěn)定；第三步：測試三種排序的正確性，單獨(dú)驗(yàn)證其正確，放在一個(gè)單獨(dú)的程序中驗(yàn)證，只是驗(yàn)證一次排序的移動(dòng)次數(shù)和比較次數(shù)，以及排序的的穩(wěn)定性，測試的數(shù)據(jù)換成只有十個(gè)比較簡單的數(shù)（0到20），這里就體現(xiàn)出了為什么李春元同學(xué)為什么要用一個(gè)結(jié)構(gòu)體來表示每個(gè)數(shù)據(jù)，結(jié)構(gòu)體中既包含了關(guān)鍵字的大小，也包括了每個(gè)關(guān)鍵字的位置信息，便于判斷排序算法是否穩(wěn)定，但是實(shí)驗(yàn)中并沒有體現(xiàn)這點(diǎn)，這是考慮到了這個(gè)可能。

這部分比較簡單，沒出大問題 第四步：對計(jì)算運(yùn)行時(shí)間的函數(shù)的驗(yàn)證和整個(gè)程序的驗(yàn)證是一起進(jìn)行的，總要是通過看三種排序所花的平均時(shí)間的大小來判斷程序是否正確預(yù)計(jì)的是快速排序>（冒泡排序，簡單排序）后兩者基本相同 第五步：為了更好的體現(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í)要注意兩者的兼容性，開始時(shí)李春元同學(xué)用了c++的輸出輸入流來顯示輸出，這在linux的編譯環(huán)境下是不支持的，最后都改成了c中的printf語句以及main函數(shù)返回值不能為void還要注意的是文件的后綴是.c在linux上實(shí)現(xiàn)后，掛載到arm上再通過終端顯示實(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ù)簡單排序0.028049450500292605冒泡排序0.03004945050010838124快速排序0.019042276168218790C） （arm）終端上運(yùn)行結(jié)果：運(yùn)行時(shí)間（s）數(shù)據(jù)移動(dòng)次數(shù)比較次數(shù)簡單排序10.460049450500292605冒泡排序12.15004945050010838124快速排序7.330042276539218741存在的問題和改進(jìn)的方法； 程序中并沒有涉及到判斷排序是否是穩(wěn)定的，這是需要改進(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)，但沒有深入下去，其實(shí)到這里也算是做到了，只需在初始化時(shí)對data賦初始值，標(biāo)記每個(gè)數(shù)據(jù)的位置，移動(dòng)時(shí)整個(gè)節(jié)點(diǎn)一起移動(dòng)，最后每個(gè)節(jié)點(diǎn)完整輸出，看key相同但data值不同的節(jié)點(diǎn)相對位置是變化了，沒變則是穩(wěn)定的，反之不穩(wěn)定。

參考文獻(xiàn)【1】《數(shù)據(jù)結(jié)構(gòu)》（C語言版） 嚴(yán)蔚敏 吳偉明 編著，清華大學(xué)出版社；【2】《C語言程序設(shè)計(jì)》 譚浩強(qiáng) 著 清華大學(xué)出版社；【3】《嵌入式設(shè)計(jì)及Linux驅(qū)動(dòng)開發(fā)指南——基于ARM 9處理器》 孫天澤，袁文菊，張海峰，北京：電子工業(yè)出版社；【4】 《嵌入式linux應(yīng)用開發(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; /*定義元素結(jié)點(diǎn)類型*/typedef struct{ long 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) /*簡單選擇排序法:由小到大排列*/{ int i,j,k; recdtype t; for(i=0;icp++;/*比較一次，比較次數(shù)加一*/ } if(k!=i) { t=r[i];r[i]=r[k];r[k]=t; cm->mv+=3;/*交換次數(shù)加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; /*關(guān)鍵字移動(dòng)次數(shù)加3*/ } cm->cp++; /*執(zhí)行if語句，比較次數(shù)加1*/ j--; }/*如果無記錄交換發(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=s; int high=t; r[0]=r[s]; /*將基準(zhǔn)記錄移至r[0]中*/ while(low