基于C語(yǔ)言的多種排序方法的實(shí)現(xiàn)

1、 . . . 基于C語(yǔ)言的多種排序方法的實(shí)現(xiàn)1 引 言1.1 課題背景排序問題源遠(yuǎn)流長(zhǎng)，一直是數(shù)學(xué)地重要組成部分。隨著各種信息的快速更新，排序問題也走進(jìn)了其他領(lǐng)域以與我們地日常生活。如何高效地排序一直困擾著我們。1.2 課程設(shè)計(jì)目的排序是數(shù)學(xué)的重要組成部分，工作量大是其存在的問題。如何高效地排序？本程序就是解決這個(gè)問題而設(shè)計(jì)。程序中，把數(shù)列儲(chǔ)存在數(shù)組中，采用插入排序等十種排序方法對(duì)數(shù)組元素進(jìn)行排序，高效地解決了排序問題。本軟件開發(fā)的平臺(tái)為最新的微軟公司出版的市面最新系統(tǒng)Windows 2000，而且可以作為自身的運(yùn)行平臺(tái)非常廣泛，包括 Windows 98/2000/XP/Vista等等。1.

2、3課程設(shè)計(jì)容本程序把對(duì)數(shù)列的排序轉(zhuǎn)化為對(duì)數(shù)組元素的排序，用戶可以根據(jù)自己的實(shí)際問題選擇系統(tǒng)提供的七種排序方法的任意一種進(jìn)行排序。程序通過自身的判斷以與處理實(shí)現(xiàn)排序。程序最后輸出每趟排序與初始排序結(jié)果。 2 系統(tǒng)分析與設(shè)計(jì)方案 2.1 系統(tǒng)分析設(shè)計(jì)一個(gè)排序信息管理系統(tǒng)，使之能夠操作實(shí)現(xiàn)以下功能：1) 顯示需要輸入的排序長(zhǎng)度與其各個(gè)關(guān)鍵字2) 初始化輸入的排序序列3) 顯示可供選擇的操作菜單4) 顯示輸出操作后的移動(dòng)次數(shù)和比較次數(shù)5) 顯示操作后的新序列5) 可實(shí)現(xiàn)循環(huán)繼續(xù)操2.2 設(shè)計(jì)思路通過定義C語(yǔ)言順序表來存儲(chǔ)排序元素信息，構(gòu)造相關(guān)函數(shù)，對(duì)輸入的元素進(jìn)行相應(yīng)的處理。 22.3 設(shè)計(jì)方案設(shè)計(jì)方

3、案如圖2.1所示開始定義順序表相關(guān)函數(shù)的聲明主函數(shù)退出系統(tǒng)圖2.1 設(shè)計(jì)方案具體流程見圖2.2開始菜單插入排序冒泡排序快速排序堆排序是否繼續(xù)操作結(jié)束退出排序折半插入排序簡(jiǎn)單選擇排序 輸入數(shù)據(jù)圖2.2 程序流程圖31 / 313功能設(shè)計(jì)3.1 SqList順序表其中包括順序表長(zhǎng)度，以與順序表。源代碼如下：1typedef struct KeyType key; /關(guān)鍵字項(xiàng) InfoType otherinfo; /其他數(shù)據(jù)項(xiàng)RedType;typedef struct RedType rMaxSize+1; /r0作為監(jiān)視哨int length; /順序表長(zhǎng)度SqList;3.2 直接插入排序

4、直接插入排序是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表有序序列r1i-1無序系列rinri有序序列r1i 無序系列ri+1n 圖3.1 直接插入排序示意圖將第i個(gè)記錄的關(guān)鍵字ri.key順序地與前面記錄的關(guān)鍵字ri-1.key,ri-2.key,，r1.key進(jìn)行比較，把所有關(guān)鍵字大于ri.key的記錄依次后移一位，直到關(guān)鍵字小于或者等于ri.key的記錄rj，直接將ri插入到rj后面，循環(huán)以上過程直到最后一個(gè)紀(jì)錄也插入到合理的位置。整個(gè)排序過程是從第2個(gè)記錄開始的，視第1個(gè)記錄為已經(jīng)排好序的集合。3.3 冒泡排序 13.25 13.15 13.02 12.92

5、 12.95 13.10交換 冒泡排序是對(duì)所有相鄰的記錄進(jìn)行比較，若這兩個(gè)元素剛好與排序結(jié)果逆序，則將這兩個(gè)元素的位置進(jìn)行交換。 過程描述如下圖所示： 13.15 13.25 13.02 12.92 12.95 13.10交換交換 13.15 13.02 13.25 12.92 12.95 13.10圖3.2 冒泡排序第一趟的前三次比較 13.15 13.02 12.92 12.95 13.10 13.25圖3.3 冒泡排序的第一趟比較結(jié)果（1）、將整個(gè)的待排序序列的記錄序列劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。（2）、對(duì)無序區(qū)從前向后依次將相鄰記錄的數(shù)據(jù)進(jìn)行比

6、較，若兩結(jié)果的大小剛好與排序結(jié)果相反，則將其交換，從而始數(shù)據(jù)值大的記錄向右邊移動(dòng)。計(jì)較完無序區(qū)的最后兩個(gè)記錄，一趟冒泡排序結(jié)束。無序區(qū)最后一個(gè)記錄進(jìn)入有序區(qū)。（3）、重復(fù)步驟（2），直到無序區(qū)中只剩下一個(gè)記錄。3.4 快速排序快速排序是首先選擇一個(gè)軸值，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵均小于等于軸值，另一部分記錄的關(guān)鍵字均大于等于軸值，再分別對(duì)這兩部分繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。過程描述路下圖所示：初始關(guān)鍵字序列 72 6 57 88 60 42 83 73 48 85 i j j 進(jìn)行1次交換之后 48 6 57 88 60 42 83 73 85i i

7、j進(jìn)行2次交換之后 48 6 57 60 42 83 73 88 85I j j進(jìn)行3次交換之后 48 6 57 42 60 83 73 48 85I j j完成一趟排序 48 6 57 42 60 72 83 73 88 85圖3.4 一趟快速排序過程初始狀態(tài) 72 6 57 88 60 42 83 73 48 85一次劃分之后 48 6 57 42 60 72 83 73 48 85分別進(jìn)行快速排序 42 6 48 57 60 6 42 結(jié)束 57 60 結(jié)束 73 83 88 85 結(jié)束 85 88 結(jié)束有序序列 6 42 48 57 60 72 73 83 85 88圖3.5 快速排序

8、的完整過程3.5 堆排序 （1）、用建堆算法建立原始堆；（2）、堆尾元素與堆頂元素互換；（3）、再次調(diào)用建堆算法建堆；（4）、重復(fù)執(zhí)行步驟（2）直到所有元素排好序。過程描述：假設(shè)，待排序的序列為：36 15 53 18 45 30 48 72 93第一步，建立原始堆結(jié)構(gòu)361553184530487293361553184530487293 a、從第4個(gè)節(jié)點(diǎn)開始調(diào)整 b、對(duì)第3個(gè)節(jié)點(diǎn)進(jìn)行調(diào)整153630184530487293361530184553487293 c、對(duì)第2個(gè)節(jié)點(diǎn)進(jìn)行調(diào)整 d、連續(xù)向下篩選151830364553487293e、原始堆 圖3.6 建立原始堆第二步，15與93交換

9、位置后，重新調(diào)整為堆，18為堆頂元素1893183036455348721536307245534893153093圖3.7 第二次調(diào)整36483036539345724572485315181815圖3.8 第三次調(diào)整3.6 折半插入排序因?yàn)?R1.i-1 是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。如同直接插入排序，只是確定插入的位置時(shí)，選擇折半查找的方法。7、簡(jiǎn)單選擇排序假設(shè)排序過程中，待排記錄序列的狀態(tài)為：無序序列 Ri.n有序序列R1.i-1圖3.9 待排序記錄序列排序過程：第i簡(jiǎn)單選擇排序，從無序序列

10、中選擇最小的一個(gè)元素，插入到有序序列當(dāng)中去。有序序列R1.i無序序列 Ri+1.n4 運(yùn)行結(jié)果圖3.10 進(jìn)行一趟簡(jiǎn)單選擇排序后得序列4 技術(shù)難點(diǎn)與分析4.1 將四個(gè)子程序串成一個(gè)整體 解決方法：通過編寫一個(gè)主程序4void main()int i,k;char ch='y'SqList *l; l=(SqList *)malloc(sizeof(SqList );while(ch='y')InsertSort(l,m,n);BubbleSort(l,1,l->length); 子程序調(diào)用QuickSort(l,1,l->length);HeapSo

11、rt(l);printf("n是否繼續(xù)操作(y/n):");getchar();ch=getchar();對(duì)四個(gè)子程序進(jìn)行調(diào)用，始之構(gòu)成一個(gè)整體。4.2 如何對(duì)四個(gè)子程序的比較和移動(dòng)次數(shù)進(jìn)行定義如果都采用整體變量，則在執(zhí)行過程中會(huì)出現(xiàn)數(shù)據(jù)累加現(xiàn)象，導(dǎo)致計(jì)算結(jié)果出錯(cuò)，故在定義過程中部分采用整體變量，部分采用局部變量，以此來避免產(chǎn)生沖突。整體變量執(zhí)行一次之后的結(jié)果如圖4.1所示：圖4.1 采用整體變量執(zhí)行一次 整體變量執(zhí)行二次之后的結(jié)果如圖4.2所示：出現(xiàn)數(shù)據(jù)累加現(xiàn)象圖4.2采用整體變量執(zhí)行二次整體和局部變量并用執(zhí)行兩次的結(jié)果如圖4.3所示，無數(shù)據(jù)累加情況圖4.3 整體和局部變

12、量并用執(zhí)行兩次5系統(tǒng)測(cè)試5.1 系統(tǒng)主界面圖5.1 系統(tǒng)主界面5.2 直接插入排序測(cè)試圖5.2 直接插入排序測(cè)試5.3 冒泡排序測(cè)試圖5.3 冒泡排序測(cè)試結(jié)果5.4 快速選擇排序測(cè)試圖5.4 快速選擇排序測(cè)試結(jié)果5.5 堆排序測(cè)試圖5.5 堆排序測(cè)試結(jié)果5.6 折半插入排序圖5.6 折半插入排序測(cè)試結(jié)果5.7 簡(jiǎn)單選擇排序圖5.7 簡(jiǎn)單選擇排序6 結(jié)束語(yǔ)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)和現(xiàn)代計(jì)算機(jī)技術(shù)的實(shí)際應(yīng)用相結(jié)合，是我們?cè)诒緦W(xué)期學(xué)完理論課程之后對(duì)自己學(xué)習(xí)能力的一次很好的檢驗(yàn)，從開始的算法思路到運(yùn)行調(diào)試后的可執(zhí)行程序，都是一個(gè)很好的學(xué)習(xí)和鍛煉的過程。既可以使我們鞏固了原有的理論知識(shí)，培養(yǎng)了我們靈活運(yùn)用和組合

13、集成所學(xué)過知識(shí)與技能來分析、解決實(shí)際問題的能力，也可以使我們體會(huì)到自身知識(shí)和能力能在實(shí)際中的應(yīng)用和發(fā)揮。不但可以激發(fā)創(chuàng)新意識(shí)，還可以開發(fā)創(chuàng)造能力、培養(yǎng)溝通能力。這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的時(shí)間里雖然時(shí)間有限，但確實(shí)使我受益非淺。通過實(shí)踐課程設(shè)計(jì)我豐富了編譯工具操作經(jīng)驗(yàn)，更加深了對(duì)C語(yǔ)言的了解，熟悉了其環(huán)境，更增強(qiáng)了對(duì)排序算法的理解與運(yùn)用。而且，在完成本課程設(shè)計(jì)的過程中，也充滿磨練了我的意志，鍛煉了我的耐心、認(rèn)真。在實(shí)踐的過程中，需要不斷的查閱資料，甚至需要求助于老師、同學(xué)。在課程設(shè)計(jì)中要善于思考，多動(dòng)手。我深知，獨(dú)立完成這樣一項(xiàng)任務(wù)需要克服許多困難。總之，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)讓我受益良多，我會(huì)好好珍惜像

14、這種難得的機(jī)會(huì)，努力學(xué)習(xí)知識(shí)。也感幫助了我的老師、同學(xué)。參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.：清華大學(xué)，19972 譚浩強(qiáng)，C程序設(shè)計(jì)（第三版）.：清華大學(xué)，20053譚浩強(qiáng)，C語(yǔ)言程序設(shè)計(jì)題解與上機(jī)指導(dǎo)(第三版).：清華大學(xué)，20054Jeri R.Hanly，Elliot B. Koffman，問題求解與程序設(shè)計(jì)C語(yǔ)言版（第四版）.：清華大學(xué)，2007-15何欽銘，顏暉，C語(yǔ)言設(shè)計(jì)教程.:高等教育，2008年6 吳文虎，程序設(shè)計(jì)基礎(chǔ).:清華大學(xué)，2003附 錄 ：系統(tǒng)源程序代碼#include<stdio.h>#include<stdlib.h>#in

15、clude<malloc.h>#define MaxSize 10 /順序表的最大長(zhǎng)度typedef int KeyType; /定義關(guān)鍵字的類型為整數(shù)類型typedef int InfoType; /定義其他類型為整數(shù)類型int ptime=0;int a=0,b=0,c=0,d=0; /置快速排序和堆排序的移動(dòng)和比較次數(shù)typedef struct KeyType key; /關(guān)鍵字項(xiàng) InfoType otherinfo; /其他數(shù)據(jù)項(xiàng)RedType;typedef struct RedType rMaxSize+1; /r0作為監(jiān)視哨int length; /順序表長(zhǎng)度Sq

16、List;void print(SqList *l)int i;for(i=1;i<=l->length;i+)printf("%5d",l->ri.key);printf("n");/-/直接插入排序void InsertSort(SqList *l,int m,int n)/對(duì)數(shù)組元素r1到rl->length中的n個(gè)元素進(jìn)行直接插入排序 /r0中的容不作為排序數(shù)據(jù)，作為一個(gè)標(biāo)記又稱為監(jiān)視哨int i,j;for(i=2;i<=l->length;i+) /n-1次循環(huán)l->r0=l->ri; /將需要

17、插入的值ri賦值給r0,設(shè)置監(jiān)視哨j=i-1;m+;while(l->r0.key<l->rj.key&&+n) /查找插入位置l->rj+1=l->rj; /前值覆蓋后值j-;m+;l->rj+1=l->r0; /將原ri中的記錄存入第j+1個(gè)位置printf("第%d趟排序結(jié)果為:",i-1); print(l);printf("直接插入排序的移動(dòng)次數(shù)為：%d,比較次數(shù)為：%dn",m,n);/-/冒泡排序void BubbleSort(SqList *l,int m,int n)int i,

18、j,k=0; RedType temp;for(i=l->length;i>1;i-) /n-1趟比較for(j=1;j<i;j+) /前后兩個(gè)記錄的數(shù)據(jù)大小剛好相反if(l->rj.key>l->rj+1.key&&+n)temp=l->rj; /交換數(shù)據(jù)l->rj=l->rj+1;l->rj+1=temp;m=m+3;k+;printf("第%d趟排序結(jié)果為:",k); print(l);printf("冒泡排序的移動(dòng)次數(shù)為：%d,比較次數(shù)為：%dn",m,n);/-/快速排

19、序void QuickSort (SqList *l, int Left,int Right) int i,j,temp; i=Left;j=Right;temp=l->ri.key;/設(shè)置初始的排序區(qū) /將i和j分別記錄待排序區(qū)域的最左側(cè)記錄和最右側(cè)記錄的位置 while(i<j) while (i<j&&temp<=l->rj.key) /從右側(cè)開始掃描 j-; b+; /找到第一個(gè)小于基準(zhǔn)記錄的數(shù)據(jù) l->ri=l->rj;/覆蓋l->ri a+; while (i<j&&l->ri.key<

20、;=temp) /從右側(cè)開始掃描 i+; b+; /找到第一個(gè)大于基準(zhǔn)記錄的數(shù)據(jù)l->rj=l->ri; /覆蓋l->rja+; l->ri.key=temp;/找到正確位置 a+; ptime+; printf("第%d次劃分排序?yàn)?",ptime); print(l); if (Left<i-1) QuickSort(l,Left,i-1); /遞歸調(diào)用對(duì)左側(cè)分區(qū)域再進(jìn)行快速排序 if (i+1<Right) QuickSort(l,i+1,Right); /遞歸調(diào)用對(duì)右側(cè)分區(qū)域再進(jìn)行快速排序 /-/堆排序/調(diào)整l->rx的關(guān)鍵

21、字使l->rx.y成為一個(gè)大堆void HeapAdjust(SqList *l, int x,int y)int j;l->r0=l->rx ;for(j=2*x;j<=y;j=j*2)if(j<y&&l->rj.key<l->rj+1.key)+j;/j為key值較大的記錄下標(biāo) d+;if(l->r0.key>l->rj.key)d+;break;l->rx=l->rj;c+;x=j;l->rx=l->r0;c+;/對(duì)順序表l進(jìn)行堆排序void HeapSort(SqList *l)i

22、nt i,j;for(i=l->length/2;i>=0;-i) /將l->r1.i建成初始堆HeapAdjust(l,i,l->length);printf("初始序列建成堆：");print(l);for(j=l->length;j>1;-j) /對(duì)當(dāng)前l(fā)->r1.i進(jìn)行堆排序，共做n-1趟l->r0=l->rj;l->rj=l->r1;l->r1=l->r0;c=c+3;HeapAdjust(l,1,j-1);printf("第%d趟建堆結(jié)果為:",l->leng

23、th-j+1);print(l); void BinSort (SqList *l, int length)/*對(duì)記錄數(shù)組r進(jìn)行折半插入排序，length為數(shù)組的長(zhǎng)度*/int i,j;RedType x;int low,high,mid;for ( i=2; i<=length ; +i ) x=l-> ri;low=1; high=i-1;while (low<=high ) /* 確定插入位置*/ mid=(low+high) / 2;if ( x.key<l-> rmid.key ) high=mid-1;else low=mid+1;for ( j=i-

24、1 ; j>= low; -j ) l->rj+1= l->rj; /* 記錄依次向后移動(dòng) */ l->rlow=x; /* 插入記錄 */ printf("第%d趟排序結(jié)果為:",i-1); print(l);/*BinSort*/void SelectSort(SqList *l, int length)/*對(duì)記錄數(shù)組r做簡(jiǎn)單選擇排序，length為數(shù)組的長(zhǎng)度*/int i,j,k;int n;RedType x; n=length;for ( i=1 ; i<= n-1; +i) k=i;for ( j=i+1 ; j<= n ;

25、+j) if (l->rj.key < l->rk.key ) k=j;if ( k!=i) x= l->ri; l->ri= l->rk;l->rk=x;printf("第%d趟排序結(jié)果為:",i); print(l); /* SelectSort */ void main()int i,k;char ch='y'SqList *l; l=(SqList *)malloc(sizeof(SqList );while(ch='y')int m=0,n=0; /置直接插入排序和冒泡排序的移動(dòng)和比較次數(shù)p

26、rintf("nnn"); printf("ttn");printf("tt#*#*#*#*歡迎進(jìn)入排序管理系統(tǒng)*#*#*#*#n");printf("ttn");printf("nnn");printf("如果碰到意外結(jié)束的情況或者排序不正確的情況，請(qǐng)與時(shí)聯(lián)系管理員立強(qiáng)、nn");printf("本系統(tǒng)為免費(fèi)系統(tǒng)，如帶來任何問題，自己負(fù)責(zé)、nn");printf("tt歡迎使用排序管理系統(tǒng)n"); printf("tt 請(qǐng)選

27、擇所需功能: n");printf("tt 1.直接插入排序 n");printf("tt 2.冒泡排序 n");printf("tt 3.快速排序 n");printf("tt 4.堆排序 n");printf("tt 5.折半插入排序 n");printf("tt 6.簡(jiǎn)單選擇排序 n");printf("tt 7.退出系統(tǒng) n");printf("tt歡迎使用排序管理系統(tǒng)n");printf("nnn"

28、;);printf("請(qǐng)選擇：");scanf("%d",&k);switch (k)case 1:printf("n您選擇的是直接插入排序：n"); printf("輸入要排序列表的長(zhǎng)度n："); scanf("%d",&l->length); for(i=1;i<=l->length;i+) printf("輸入第%d個(gè)記錄的關(guān)鍵字：",i); scanf("%d",&l->ri.key); printf

29、("初始輸入序列為："); print(l); InsertSort(l,m,n); printf("直接插入排序后記錄為:"); print(l); break;case 2:printf("n您選擇的是冒泡排序：n"); printf("輸入要排序列表的長(zhǎng)度n："); scanf("%d",&l->length); for(i=1;i<=l->length;i+) printf("輸入第%d個(gè)記錄的關(guān)鍵字：",i); scanf("%d

30、",&l->ri.key); printf("初始輸入序列為："); print(l); BubbleSort(l,1,l->length); printf("冒泡排序后記錄為："); print(l); break; case 3:printf("n您選擇的是快速排序：n"); printf("輸入要排序列表的長(zhǎng)度n："); scanf("%d",&l->length); for(i=1;i<=l->length;i+) printf(&

31、quot;輸入第%d個(gè)記錄的關(guān)鍵字：",i); scanf("%d",&l->ri.key); printf("初始輸入序列為："); print(l); QuickSort(l,1,l->length); printf("快速排序的移動(dòng)次數(shù)為：%d,比較次數(shù)為：%dn",a,b); printf("快速排序后記錄為:"); print(l); break; case 4:printf("n您選擇的是堆排序：n"); printf("輸入要排序列表的長(zhǎng)度n

32、："); scanf("%d",&l->length); for(i=1;i<=l->length;i+) printf("輸入第%d個(gè)記錄的關(guān)鍵字：",i); scanf("%d",&l->ri.key); printf("初始輸入序列為："); print(l); HeapSort(l); printf("堆排序的移動(dòng)次數(shù)為：%d,比較次數(shù)為：%dn",c,d); printf("堆排序后記錄為："); print(l);

33、 break; case 5:printf("n您選擇的是折半插入排序：n"); printf("輸入要排序列表的長(zhǎng)度n："); scanf("%d",&l->length); for(i=1;i<=l->length;i+) printf("輸入第%d個(gè)記錄的關(guān)鍵字：",i); scanf("%d",&l->ri.key); printf("初始輸入序列為："); print(l); BinSort (l,l->length);

34、 printf("快速排序后記錄為:"); print(l); break; case 6:printf("n您選擇的是簡(jiǎn)單選擇排序：n"); printf("輸入要排序列表的長(zhǎng)度n："); scanf("%d",&l->length); for(i=1;i<=l->length;i+) printf("輸入第%d個(gè)記錄的關(guān)鍵字：",i); scanf("%d",&l->ri.key); printf("初始輸入序列為："); print(l); SelectSort(l, l->length); printf("快速排序后記錄為:"); print(l); break; case 7:break;default:printf("沒有找到你需要的排序方法"); break;printf("n是否繼續(xù)操作(