排序算法比較程序課程設(shè)計(jì)

1、 操作系統(tǒng)課程設(shè)計(jì)報(bào)告題 目： 排序算法比較程序 班 級(jí)： 學(xué) 號(hào)： 作者姓名： 指導(dǎo)教師： 2012年6月6日目 錄1設(shè)計(jì)題目與要求- 2 -1.1實(shí)驗(yàn)?zāi)康? 2 -1.2設(shè)計(jì)要求- 2 -1.3 初始條件- 2 -2總體設(shè)計(jì)思想及過程及相關(guān)知識(shí)- 2 -2.1總體設(shè)計(jì)思想及過程- 2 -2.2開發(fā)環(huán)境與工具- 3 -3程序各模塊流程圖- 4 -3.1 主程序模塊- 4 -3.2 冒泡排序模塊- 5 -3.3 選擇排序模塊- 6 -4源程序代碼- 6 -6課程總結(jié)- 14 -7參考文獻(xiàn)- 14 -1 設(shè)計(jì)題目與要求1.1實(shí)驗(yàn)?zāi)康耐ㄟ^用不同的算法實(shí)現(xiàn)排序問題，使我們深入了解和掌握同一問題可用不

2、同算法解決，從而明白一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至整個(gè)程序的效率。1.2設(shè)計(jì)要求（1） 開發(fā)一款排序算法，由用戶輸入長度可變的內(nèi)容：要求容錯(cuò)檢查：存在字母則做字符排序，輸入均為數(shù)字則按值排序（2） 提供兩種以上的排序方法供用戶選擇（3） 排序并顯示最終結(jié)果及執(zhí)行時(shí)間1.3 初始條件（1）操作系統(tǒng)：windows（2）程序設(shè)計(jì)語言: c、c+ (兩種語言的結(jié)合，是為了簡化代碼的編寫)2 總體設(shè)計(jì)思想及過程及相關(guān)知識(shí)2.1總體設(shè)計(jì)思想及過程冒泡排序：1. 基本思想：兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。2. 排序過程：依次比較相鄰的兩

3、個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。選擇排序：1. 基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最小

4、（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2.排序過程：第一趟排序在所有待排序的n個(gè)記錄中選出關(guān)鍵字最小的記錄，將它與數(shù)據(jù)表中的第一個(gè)記錄交換位置，使關(guān)鍵字最小的記錄處于數(shù)據(jù)表的最前端；第二趟在剩下的n-1個(gè)記錄中再選出關(guān)鍵字最小的記錄，將其與數(shù)據(jù)表中的第二個(gè)記錄交換位置，使關(guān)鍵字次小的記錄處于數(shù)據(jù)表的第二個(gè)位置；重復(fù)這樣的操作，依次選出數(shù)據(jù)表中關(guān)鍵字第三小、第四小的元素，將它們分別換到數(shù)據(jù)表的第三、第四個(gè)位置上。排序共進(jìn)行n-1趟，最終可實(shí)現(xiàn)數(shù)據(jù)表的升序排列。2.2開發(fā)環(huán)境與工具系統(tǒng)平臺(tái)：windows環(huán)境實(shí)現(xiàn)語言：cc+開發(fā)工具：vc+6.03 程序

5、各模塊流程圖3.1 主程序模塊3.2 冒泡排序模塊3.3 選擇排序模塊4源程序代碼實(shí)驗(yàn)要求：（1） 開發(fā)一款排序算法，由用戶輸入長度可變的內(nèi)容：要求容錯(cuò)檢查：存在字母則做字符排序，輸入均為數(shù)字則按值排序（2） 提供兩種以上的排序方法供用戶選擇（3） 排序并顯示最終結(jié)果及執(zhí)行時(shí)間#include#include#include#define max 100using namespace std;typedef struct/定義一個(gè)結(jié)構(gòu)體,保存key int key;datatype;/結(jié)構(gòu)體的別名typedef struct/定義一個(gè)結(jié)構(gòu)體,保存length。character datatyp

6、e rmax+1; int length; int character;sqlist,*psqlist;/結(jié)構(gòu)體的別名（主要好處是：每次聲明結(jié)構(gòu)體時(shí)只要用sqlist,*psqlist去聲明就可以了，節(jié)省代碼)typedef struct/定義一個(gè)結(jié)構(gòu)體 char dmax+1; int length;list,*plist;/同樣是結(jié)構(gòu)體的別名psqlist bubblesort(psqlist s)/第1種方法(冒泡排序，輸入順序表) int i,j,temp; for(i=0;ilength;i+)/排序趟數(shù)的循環(huán) for(j=0;jlength-i-1;j+)/每趟排序中每個(gè)字符的循環(huán)

7、 if(s-rj.keys-rj+1.key)/前后兩個(gè)字符的判斷 temp=s-rj.key;/賦值運(yùn)算s-rj.key=s-rj+1.key;/將小的排在前面，大的排在后面s-rj+1.key=temp;/兩個(gè)字符的位置變換 return s;psqlist selectsort(psqlist s)/第2種方法(選擇排序，輸入順序表) int i,j,k,min; /min為每次查找到的最小的數(shù) for(i=0;ilength;i+)/每趟排序中每個(gè)字符的循環(huán) min=s-ri.key;/找出最小的那個(gè)元素k=i; for(j=i+1;jlength;j+) if(s-rj.keyrj.

8、key; k=j; s-rk.key=s-ri.key;s-ri.key=min; return s;plist creat_plist()/順序表的創(chuàng)建 plist s; /*建立字符順序表*/ char ch; int i=0; /*i為第幾個(gè)字符*/ s=(plist)malloc(sizeof(list); cout請(qǐng)輸入一串?dāng)?shù)據(jù):di=ch;i+;s-length=i; s-di=0; return s;psqlist judge(plist s)/加載判斷函數(shù)，判斷是否為全數(shù)字，入口參數(shù)：字符串順序表 int i,j=0; /*i為循環(huán)數(shù)，j為判斷數(shù)*/ psqlist t; /*

9、建立數(shù)字順序表*/ t=(psqlist)malloc(sizeof(sqlist); for(i=0;ilength;i+) if(s-didi=9)j=1; /*若為全數(shù)字，j=1,否則j=0*/ if(j=0) /*全為數(shù)字，將數(shù)字存入數(shù)字順序表中*/ for(i=0;ilength;i+)t-ri.key=s-di-0;t-character=0; else /*有字符，將字符的ascll碼存入字符順序表中*/ for(i=0;ilength;i+)t-ri.key=s-di;t-character=1; t-length=s-length;return t;int main()/主函

10、數(shù) plist s; psqlist t; int i,chose; double cost_time; clock_t start,end; start=clock(); /開始時(shí)間計(jì)數(shù) s=creat_plist(); t=judge(s); cout請(qǐng)選擇：1.輸入1，冒泡排序 2.輸入2，選擇排序chose; if(chose=1)/選擇第1種方法 bubblesort(t); else if(chose=2)/選擇第2種方法 selectsort(t); else/容錯(cuò)檢查，輸入的數(shù)字若不是1或2，則表示輸入錯(cuò)誤 cout輸入錯(cuò)誤，按任意鍵退出。endl;return 0; cout

11、character=0) for(i=0;ilength;i+) printf(%d,t-ri.key); else for(i=0;ilength;i+)printf(%c,t-ri.key); coutendl; end=clock(); /結(jié)束時(shí)間計(jì)數(shù) cost_time=(double)(end-start)/clocks_per_sec);/中間耗時(shí) printf(所用時(shí)間為:%fs,n,cost_time); return 1;5測試及結(jié)果6課程總結(jié)做了這次程序設(shè)計(jì)，我們覺得利用c+進(jìn)行編程并不像想像中的那么高深，尤其像我們現(xiàn)在所做的，只是一些最基本的程序。經(jīng)過一個(gè)學(xué)期的學(xué)習(xí)，對(duì)c+有了一個(gè)初步的認(rèn)識(shí)，但沒有進(jìn)行實(shí)際應(yīng)用。這次程序設(shè)計(jì)，就相當(dāng)于對(duì)一個(gè)學(xué)期的所學(xué)做一個(gè)總結(jié)，再進(jìn)行一次綜合運(yùn)用，更是學(xué)到了很多新的東西，比如在做的程序中，對(duì)各種頭文件都更加熟悉了，無意中也提升了自己的c+設(shè)計(jì)水平；又比如在程序設(shè)計(jì)過程中碰到了很多問題，通過上網(wǎng)查資料等各種手段，我們的解決實(shí)際問題的能力也得到了提高。然而我們知道，我們現(xiàn)在所掌握的知識(shí)，整個(gè)程序設(shè)計(jì)領(lǐng)域，甚至只在c+的設(shè)計(jì)領(lǐng)域中，都還只是皮毛階段，以后想要這方面發(fā)展提高，就必須做出更大的努力。這次的程序設(shè)計(jì)，使我們對(duì)編程產(chǎn)生了濃厚的興趣，并讓我們對(duì)編程有了一個(gè)更