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

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

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

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

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

5、 12.95 13.10交換 冒泡排序是對所有相鄰的記錄進行比較，若這兩個元素剛好與排序結(jié)果逆序，則將這兩個元素的位置進行交換。 過程描述如下圖所示： 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）、將整個的待排序序列的記錄序列劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。（2）、對無序區(qū)從前向后依次將相鄰記錄的數(shù)據(jù)進行比

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

7、j進行2次交換之后 48 6 57 60 42 83 73 88 85I j j進行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分別進行快速排序 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）、重復執(zhí)行步驟（2）直到所有元素排好序。過程描述：假設，待排序的序列為：36 15 53 18 45 30 48 72 93第一步，建立原始堆結(jié)構(gòu)361553184530487293361553184530487293 a、從第4個節(jié)點開始調(diào)整 b、對第3個節(jié)點進行調(diào)整153630184530487293361530184553487293 c、對第2個節(jié)點進行調(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 折半插入排序因為 R1.i-1 是一個按關鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在R1.i-1中查找Ri的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。如同直接插入排序，只是確定插入的位置時，選擇折半查找的方法。7、簡單選擇排序假設排序過程中，待排記錄序列的狀態(tài)為：無序序列 Ri.n有序序列R1.i-1圖3.9 待排序記錄序列排序過程：第i簡單選擇排序，從無序序列

10、中選擇最小的一個元素，插入到有序序列當中去。有序序列R1.i無序序列 Ri+1.n4 運行結(jié)果圖3.10 進行一趟簡單選擇排序后得序列4 技術(shù)難點與分析4.1 將四個子程序串成一個整體 解決方法：通過編寫一個主程序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();對四個子程序進行調(diào)用，始之構(gòu)成一個整體。4.2 如何對四個子程序的比較和移動次數(shù)進行定義如果都采用整體變量，則在執(zhí)行過程中會出現(xiàn)數(shù)據(jù)累加現(xiàn)象，導致計算結(jié)果出錯，故在定義過程中部分采用整體變量，部分采用局部變量，以此來避免產(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)測試5.1 系統(tǒng)主界面圖5.1 系統(tǒng)主界面5.2 直接插入排序測試圖5.2 直接插入排序測試5.3 冒泡排序測試圖5.3 冒泡排序測試結(jié)果5.4 快速選擇排序測試圖5.4 快速選擇排序測試結(jié)果5.5 堆排序測試圖5.5 堆排序測試結(jié)果5.6 折半插入排序圖5.6 折半插入排序測試結(jié)果5.7 簡單選擇排序圖5.7 簡單選擇排序6 結(jié)束語數(shù)據(jù)結(jié)構(gòu)課程設計和現(xiàn)代計算機技術(shù)的實際應用相結(jié)合，是我們在本學期學完理論課程之后對自己學習能力的一次很好的檢驗，從開始的算法思路到運行調(diào)試后的可執(zhí)行程序，都是一個很好的學習和鍛煉的過程。既可以使我們鞏固了原有的理論知識，培養(yǎng)了我們靈活運用和組合

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

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

15、clude<malloc.h>#define MaxSize 10 /順序表的最大長度typedef int KeyType; /定義關鍵字的類型為整數(shù)類型typedef int InfoType; /定義其他類型為整數(shù)類型int ptime=0;int a=0,b=0,c=0,d=0; /置快速排序和堆排序的移動和比較次數(shù)typedef struct KeyType key; /關鍵字項 InfoType otherinfo; /其他數(shù)據(jù)項RedType;typedef struct RedType rMaxSize+1; /r0作為監(jiān)視哨int length; /順序表長度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)/對數(shù)組元素r1到rl->length中的n個元素進行直接插入排序 /r0中的容不作為排序數(shù)據(jù)，作為一個標記又稱為監(jiān)視哨int i,j;for(i=2;i<=l->length;i+) /n-1次循環(huán)l->r0=l->ri; /將需要

17、插入的值ri賦值給r0,設置監(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個位置printf("第%d趟排序結(jié)果為:",i-1); print(l);printf("直接插入排序的移動次數(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+) /前后兩個記錄的數(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("冒泡排序的移動次數(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;/設置初始的排序區(qū) /將i和j分別記錄待排序區(qū)域的最左側(cè)記錄和最右側(cè)記錄的位置 while(i<j) while (i<j&&temp<=l->rj.key) /從右側(cè)開始掃描 j-; b+; /找到第一個小于基準記錄的數(shù)據(jù) l->ri=l->rj;/覆蓋l->ri a+; while (i<j&&l->ri.key<

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

21、字使l->rx.y成為一個大堆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值較大的記錄下標 d+;if(l->r0.key>l->rj.key)d+;break;l->rx=l->rj;c+;x=j;l->rx=l->r0;c+;/對順序表l進行堆排序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) /對當前l(fā)->r1.i進行堆排序，共做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)/*對記錄數(shù)組r進行折半插入排序，length為數(shù)組的長度*/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; /* 記錄依次向后移動 */ l->rlow=x; /* 插入記錄 */ printf("第%d趟排序結(jié)果為:",i-1); print(l);/*BinSort*/void SelectSort(SqList *l, int length)/*對記錄數(shù)組r做簡單選擇排序，length為數(shù)組的長度*/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; /置直接插入排序和冒泡排序的移動和比較次數(shù)p

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

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.簡單選擇排序 n");printf("tt 7.退出系統(tǒng) n");printf("tt歡迎使用排序管理系統(tǒng)n");printf("nnn"

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

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

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

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

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

34、 printf("快速排序后記錄為:"); print(l); break; case 6:printf("n您選擇的是簡單選擇排序：n"); printf("輸入要排序列表的長度n："); scanf("%d",&l->length); for(i=1;i<=l->length;i+) printf("輸入第%d個記錄的關鍵字：",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ù)操作(