內(nèi)部排序算法比較實(shí)驗(yàn)報(bào)告(c語言版)

1、word文檔可自由復(fù)制編輯【實(shí)習(xí)報(bào)告J題目：編制一個(gè)演示內(nèi)部排序算法比較的程序 班級： 姓名： 學(xué)號：完成日期： 一、需求分析1 .本演示程序?qū)σ韵?6種常用的內(nèi)部排序算法進(jìn)行實(shí)測比較：起泡排序，直接插入排序，簡單選擇排序， 快速排序，希爾排序，堆排序。2 .待排序表的元素的關(guān)鍵字為整數(shù)。比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)(關(guān)鍵字交換記為3次移動)。3 .演示程序以以用戶和計(jì)算機(jī)的對話方式執(zhí)行，在計(jì)算機(jī)終端上顯示提示信息，對隨機(jī)數(shù)組進(jìn)行排序，并 輸出比較指標(biāo)值。4 .最后對結(jié)果作出簡單分析。二、概要設(shè)計(jì)1 .可排序表的抽象數(shù)據(jù)類型定義：ADT OrderableList數(shù)據(jù)對

2、象：D=ai|ai G IntegerSet,i=1,2, ,n,n >0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,ai D,i=2,n基本操作：InitList(n)操作結(jié)果：構(gòu)造一個(gè)長度為n,元素值依次為1, 2,n的有序表。RandomizeList(d,isInverseOrder)操作結(jié)果：首先根據(jù)isInverseOrder 為True或False,將表置為逆序或正序，然后將表進(jìn)行d(0<d<8)級隨機(jī)打亂。d為0時(shí)表不打亂，d越大，打亂程度越高。RecallList()操作結(jié)果：恢復(fù)最后一次用RandomizeList隨機(jī)打亂得到的可排序表。Li

3、stLength()操作結(jié)果：返回可排序表的長度。ListEmpty()操作結(jié)果：若可排序表為空表，則返回 Ture,否則返回FalseBubbleSort( &c, &s)C和移動次數(shù)SoC和移動次數(shù)SoC和移動次數(shù)SoC和移動次數(shù)SoC和移動次數(shù)SoC和移動次數(shù)So操作結(jié)果：進(jìn)行起泡排序，返回關(guān)鍵字比較次數(shù)InsertSort( &c, &s)操作結(jié)果：進(jìn)行插入排序，返回關(guān)鍵字比較次數(shù)SelectSort ( &c, &s)操作結(jié)果：進(jìn)行選擇排序，返回關(guān)鍵字比較次數(shù)QuickSort(&c, &s)操作結(jié)果：進(jìn)行快速排序，返回

4、關(guān)鍵字比較次數(shù)ShellSort(long &c, long &s)操作結(jié)果：進(jìn)行希爾排序，返回關(guān)鍵字比較次數(shù)HeapSort (&c, &s)操作結(jié)果：進(jìn)行堆排序，返回關(guān)鍵字比較次數(shù)ListTraverse(visit()操作結(jié)果：依次對 L中的每個(gè)元素調(diào)用函數(shù) visit()ADT OrderableList2 .本程序包含兩個(gè)模塊：1)主程序模塊void main()初始化；do接受命令；處理命令；while(“命令”！= “退出”)；2)可排序表單元模塊一一實(shí)現(xiàn)可排序表的抽象數(shù)據(jù)類型；各模塊之間的調(diào)用關(guān)系如下：主程序模塊可排序表單元模塊三、詳細(xì)設(shè)計(jì)1.根

5、據(jù)題目要求和可排序表的基本操作特點(diǎn)，可排序表采用整數(shù)順序表存儲結(jié)構(gòu)。/可排序表的元素類型#define MAXSIZE 10000typedef int BOOL;typedef structint key; RedType;typedef struct LinkListRedType rMAXSIZE;int Length; LinkList;int RandArrayMAXSIZE;/內(nèi)部操作void RandomNum()int i;srand(20000);for (i = 0; i < MAXSIZE; i+)RandArrayi = (int)rand();/用作示例的順序表

6、的最大長度/關(guān)鍵字項(xiàng)/記錄類型/順序表長度/構(gòu)建隨機(jī)序列void InitLinkList(LinkList *L) /建立表int i;memset(L, 0, sizeof(LinkList);RandomNum();for (i = 0; i < MAXSIZE; i+)L->ri.key = RandArrayi;/ 賦值L->Length = i;bool LT(int i, int j, int *CmpNum) /比較 i 與 j 大小，返回 0 或 1(*CmpNum)+;if (i < j)return TRUE;elsereturn FALSE;vo

7、id Display(LinkList *L) /存儲表到 SortRes.txt 文件中FILE *f;int i;if (f = fopen("SortRes.txt", "w") = NULL)printf("can't open filen");exit(0);for (i = 0; i < L->Length; i+)fprintf(f, "%dn", L->ri.key);fclose(f);/部分操作的偽碼算法/希爾排序void ShellInsert(LinkList *L

8、, int dk, int *CmpNum, int *ChgNum)int i, j;RedType Temp;for (i = dk; i < L->Length; i+)if (LT(L->ri.key, L->ri - dk.key, CmpNum)memcpy(&Temp, &L->ri, sizeof(RedType);for (j = i - dk; j >= 0 && LT(Temp.key, L->rj.key, CmpNum); j -= dk) (*ChgNum)+;memcpy(&L-&g

9、t;rj + dk, &L->rj, sizeof(RedType);memcpy(&L->rj + dk, &Temp, sizeof(RedType);void ShellSort(LinkList *L, int dlta口，int t, int *CmpNum, int *ChgNum)int k;for (k = 0; k < t; k+)ShellInsert(L, dltak, CmpNum, ChgNum);/快速排序int Partition(LinkList *L, int low, int high, int *CmpNum, i

10、nt *ChgNum) RedType Temp;int PivotKey;memcpy(&Temp, &L->rlow, sizeof(RedType);PivotKey = L->rlow.key;while (low < high)while (low < high && L->rhigh.key >= PivotKey)high-;(*CmpNum)+;(*ChgNum)+;memcpy(&L->rlow, &L->rhigh, sizeof(RedType);while (low <

11、 high && L->rlow.key <= PivotKey)low+;(*CmpNum)+;(*ChgNum)+;memcpy(&L->rhigh, &L->rlow, sizeof(RedType);memcpy(&L->rlow, &Temp, sizeof(RedType);return low;void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum)int PivotLoc = 0;if (low < high)Piv

12、otLoc = Partition(L, low, high, CmpNum, ChgNum);QSort(L, low, PivotLoc - 1, CmpNum, ChgNum);QSort(L, PivotLoc + 1, high, CmpNum, ChgNum);void QuickSort(LinkList *L, int *CmpNum, int *ChgNum) QSort(L, 0, L->Length - 1, CmpNum, ChgNum);/堆排序void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int

13、 *ChgNum) RedType Temp;int j = 0;s+;memcpy(&Temp, &L->rs - 1, sizeof(RedType);for (j = 2 * s; j <= m; j *= 2)if (j < m && LT(L->rj - 1.key, L->rj.key, CmpNum)+j；if (!LT(Temp.key, L->rj - 1.key, CmpNum)break;(*ChgNum)+;memcpy(&L->rs - 1, &L->rj - 1, siz

14、eof(RedType);s = j;memcpy(&L->rs - 1, &Temp, sizeof(RedType);void HeapSort(LinkList *L, int *CmpNum, int *ChgNum)int i = 0;RedType Temp;for (i = L->Length / 2-1; i >= 0; i-)HeapAdjust(L, i, L->Length, CmpNum, ChgNum);for (i = L->Length; i > 1; i-)memcpy(&Temp, &L-&g

15、t;r0, sizeof(RedType);(*ChgNum)+;memcpy(&L->r0, &L->ri - 1, sizeof(RedType);memcpy(&L->ri - 1, &Temp, sizeof(RedType);HeapAdjust(L, 0, i - 1, CmpNum, ChgNum);/冒泡排序void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum) int i, j;RedType temp;for (i = 1; i <= MAXSIZE; i+)for

16、 (j = 1; j <= MAXSIZE - i; j+)if (!LT(L->rj.key, L->rj + 1.key, CmpNum)(*ChgNum)+;memcpy(&temp, &L->rj, sizeof(RedType);memcpy(&L->rj, &L->rj + 1, sizeof(RedType);memcpy(&L->rj + 1, &temp, sizeof(RedType);/選擇排序int SelectMinKey(LinkList *L, int k, int *Cmp

17、Num) int Min = k;for (; k < L->Length; k+)if (!LT(L->rMin.key, L->rk.key, CmpNum) Min = k;return Min;void SelSort(LinkList *L, int *CmpNum, int *ChgNum) int i, j;RedType temp;for (i = 0; i < L->Length; i+)j = SelectMinKey(L, i, CmpNum);if (i != j)(*ChgNum)+;memcpy(&temp, &L

18、->ri, sizeof(RedType);memcpy(&L->ri, &L->rj, sizeof(RedType);memcpy(&L->rj, &temp, sizeof(RedType);3.函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：mainBubbleSortsrandInsertSortSelectSortQuickSort ShellSortDisplayInitLinkList RandomNum LTHeapSort四、調(diào)試分析1 .對正序、逆序和若干不同程度隨機(jī)打亂的可排序表，進(jìn)行各種排序方法的比較測試，得到的測試數(shù)

19、據(jù)具 有較好的典型性和可比較性。通過設(shè)計(jì)和實(shí)現(xiàn)指定程序的隨機(jī)亂序算法，對偽隨機(jī)數(shù)序列的產(chǎn)生有了具體 的認(rèn)識和實(shí)踐。2 .將排序算法中的關(guān)鍵字比較和交換分別由Less和Swap兩個(gè)內(nèi)部操作實(shí)現(xiàn)，較好的解決了排序算法的關(guān)鍵字比較次數(shù)和移動次數(shù)的統(tǒng)計(jì)問題。而賦值是直接統(tǒng)計(jì)的。然后用插入排序驗(yàn)證各3 .本實(shí)習(xí)作業(yè)采用循序漸進(jìn)的策略，首先設(shè)計(jì)和實(shí)現(xiàn)可排序表的建立和隨機(jī)操作,種內(nèi)部輔助操作的正確性，進(jìn)而逐個(gè)加入其他排序算法，最后完成對測試結(jié)果的顯示。調(diào)試能力有了提高。 五、用戶手冊1 .本程序的運(yùn)行環(huán)境為 DOS#作系統(tǒng)，執(zhí)行文件為：內(nèi)部排序算法比較.exe。2 .進(jìn)入程序后即顯示文本方式的用戶界面:Q|

20、 *F: newDebuE0523T6_$exeF序方式序序序 二r.l'f.l'f.營上出 冒選以退lease Select the Operate：3.輸入1回車，即得直接插入排序的排序結(jié)果及其關(guān)鍵字比較次數(shù)和移動次數(shù)及時(shí)間輸入2回車，即得希爾排序的排序結(jié)果及其關(guān)鍵字比較次數(shù)和移動次數(shù)及時(shí)間輸入3回車，即得快速排序的排序結(jié)果及其關(guān)鍵字比較次數(shù)和移動次數(shù)及時(shí)間輸入4回車，即得堆排序的排序結(jié)果及其關(guān)鍵字比較次數(shù)和移動次數(shù)及時(shí)間輸入5回車，即得冒泡排序的排序結(jié)果及其關(guān)鍵字比較次數(shù)和移動次數(shù)及時(shí)間輸入6回車，即得選擇排序的排序結(jié)果及其關(guān)鍵字比較次數(shù)和移動次數(shù)及時(shí)間輸入7回車，即得以

21、上所有排序的排序結(jié)果及其關(guān)鍵字比較次數(shù)和移動次數(shù)及時(shí)間輸入8回車，即退出該程序六、測試結(jié)果對結(jié)果的截屏如下：*F: newDebuE0523T6_$fl_:|t ezeJn|_x排序方式CliaqeNunbep=lJ2b8b85TimeSpent=344nslease Select the Operate：*F: newDebiiE0523T6_$W_:|t eze20543205532062320673208032087321413216932171321732176321813218632189321923219332193322003221032228224932254322553225

22、932261322633226332264322653227322813229332305323053230532309323203232632334323372347323673237132377323813238232398323993240632409241032412324213242232433324373245032452324543245624613247532483324853248932492324973250032522325312531325343253432540325423255232565325653256632585258932591326033260432605

23、3260832609326253262532628263232640326473264932652326613266332674326893269227003270732710327133271732724327243272432725327262728327293273032731327383273832740327433275432754re入手XS；上出pa插冒選以退-口x20543205532M2320673208032087321413216932171321732176321813218632189321923219332193322003221032228224932254322

24、55322593226132263322633226432265322732281322933230532305323053230932320323263233432337234732367323713237732381323823239832399324M324092410324123242132422324333243732450324523245432456246132475324833248532489324923249732500325223253125313253432534325403254232552325653256532566325852589325913260332604

25、326053260832609326253262532628263232640326473264932652326613266332674326893269227003270732710327133271732724327243272432725327262728327293273032731327383273832740327433275432754=2序p 一二ere入:上出 paww冒選以退CJiageNuiibep=1903578T meSpent =4?inslease Select the Operate：word文檔可自由復(fù)制編輯排序方式Chaqe Numbe i'=11

26、5 UUbTineSpent=15nslease Select the Operate：*F: newDebiiE0523T6_$W_:|t eze2054320553206232067320803208732141321693217132173217632181321863218932192321933219332200322103222822493225432255322593226132263322633226432265322732281322933230532305323053230932320323263233432337234732367323713237732381323823

27、239832399324063240924103241232421324223243332437324503245232454324562461324753248332485324893249232497325003252232531253132534325343254032542325523256532565325663258525893259132603326043260532608326093262532625326282632326403264732649326523266132663326743268932692270032707327103271332717327243272432

28、72432725327262728327293273032731327383273832740327433275432754re入手XS；上出pa插冒選以退-口xChage NLimbe p=bb3 744328方=1序p 一二ere入:上出 paww冒選以退20543205532M23206732080320873214132169321713217321763218132186321893219232193321933220032210322282249322543225532259322613226332263322643226532273228132293323053230532305

29、3230932320323263233432337234732367323713237732381323823239832399324M3240924103241232421324223243332437324503245232454324562461324753248332485324893249232497325003252232531253132534325343254032542325523256532565325663258525893259132603326043260532608326093262532625326282632326403264732649326523266132

30、66332674326893269227003270732710327133271732724327243272432725327262728327293273032731327383273832740327433275432754lease Select the Operate：排序方式CJia5feNunbep=12932930TimeSpent=89BnsPlease Select the Operate：20543205532062320673208032087321413216932171321732176321813218632189321923219332193322003221

31、032228224932254322553225932261322633226332264322653227322813229332305323053230532309323203232632334323372347323673237132377323813238232398323993240632409241032412324213242232433324373245032452324543245624613247532483324853248932492324973250032522325312531325343253432540325423255232565325653256632585

32、2589325913260332604326053260832609326253262532628263232640326473264932652326613266332674326893269227003270732710327133271732724327243272432725327262728327293273032731327383273832740327433275432754re入手XS；上出pa插冒選以退-口xCJiageNuiibep=9982T line Spent =5 00mslease Select the Operate：*F: newDebiiE0523T6_$W

33、_:|t eze20543205532M232067320803208732141321693217132173217632181321863218932192321933219332200322103222822493225432255322593226132263322633226432265322732281322933230532305323053230932320323263233432337234732367323713237732381323823239832399324M324092410324123242132422324333243732450324523245432456

34、246132475324833248532489324923249732500325223253125313253432534325403254232552325653256532566325852589325913260332604326053260832609326253262532628263232640326473264932652326613266332674326893269227003270732710327133271732724327243272432725327262728327293273032731327383273832740327433275432754=2序p 一

35、二ere入:上出 paww冒選以退: newDebuE0523T6_$fl_:ft Jl|. exelease Select the Operate：7入排序;ompareNumber=6176620CliageNunbep=6166631TimeSpent=359nsword文檔可自由復(fù)制編輯爾排序:：onpareNumber=963962CJia5feNunber=937536T imeSpent =47ins快速排序;onpareNumber=78657ChageNumbep=29006TineSpent=0ns排序;；。mpare Numbe r=l 07713CJia5feNunbe

36、p=57110T imeSpent =16 ids冒泡排序;口 mpareNumber=12497500ChageNumber=6465918TimeSpent=890ms選擇排序;口 mpare Numbe r =1 2 5 075 電 Chage NiimhE f =49 9 06種排序算法（快速排序采對各種表長和測試組數(shù)進(jìn)行了測試，程序運(yùn)行正常。分析實(shí)測得到的數(shù)值,用“比中法”）的特點(diǎn)小結(jié)如下:測試插入排序希爾排序快速排序堆排序冒泡排序選擇排序比較次數(shù)第三多 越亂（逆）越 多少亂否差異小少亂否差異小稍多亂否差異很小最多越亂（逆）越 多越亂（逆）越 名第二多與亂否無關(guān)移動次數(shù)第二多 越亂（

37、逆）越 多約為快速排 序的兩倍第二少亂否差異較 小稍多亂否差異很 小最多越亂（逆）越 多最少正和逆序少七、附錄源程序文件名清單：052376李明內(nèi)部排序算法比較.cpp / 主程序#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>#include <windows.h>#include <winbase.h>#define MAXSIZE 5000#define TRUE 1#define FALSE 0typedef int

38、BOOL;typedef structint key; RedType;typedef struct LinkListRedType rMAXSIZE+1;int Length; LinkList;int RandArrayMAXSIZE+1;void RandomNum()int i;srand(2000);for (i = 1; i <= MAXSIZE; i+) RandArrayi = (int)rand();void InitLinkList(LinkList *L)int i;memset(L, 0, sizeof(LinkList);RandomNum();for (i =

39、 1; i <= MAXSIZE; i+)L->ri.key = RandArrayi;L->Length = i;bool LT(int i, int j, int *CmpNum) (*CmpNum)+;if (i < j)return TRUE;elsereturn FALSE;void Display(LinkList *L)FILE *f;int i;if (f = fopen("SortRes.txt", "w") = NULL) printf("can't open filen");exi

40、t(0);for (i = 0; i < L->Length; i+)fprintf(f, "%dn", L->ri.key);fclose(f);/希爾排序void ShellInsert(LinkList *L, int dk, int *CmpNum, int *ChgNum)int i, j;RedType Temp;for (i = dk; i < L->Length; i+)if (LT(L->ri.key, L->ri - dk.key, CmpNum)memcpy(&Temp, &L->ri,

41、sizeof(RedType);for (j = i - dk; j >= 0 && LT(Temp.key, L->rj.key, CmpNum); j -= dk) (*ChgNum)+;memcpy(&L->rj + dk, &L->rj, sizeof(RedType);memcpy(&L->rj + dk, &Temp, sizeof(RedType);void ShellSort(LinkList *L, int dlta口，int t, int *CmpNum, int *ChgNum)int k;fo

42、r (k = 0; k < t; k+)ShellInsert(L, dltak, CmpNum, ChgNum);/快速排序int Partition(LinkList *L, int low, int high, int *CmpNum, int *ChgNum)RedType Temp;int PivotKey;memcpy(&Temp, &L->rlow, sizeof(RedType);PivotKey = L->rlow.key;while (low < high)while (low < high && L->r

43、high.key >= PivotKey)high-;(*CmpNum)+;(*ChgNum)+;memcpy(&L->rlow, &L->rhigh, sizeof(RedType);while (low < high && L->rlow.key <= PivotKey)low+;(*CmpNum)+;(*ChgNum)+;memcpy(&L->rhigh, &L->rlow, sizeof(RedType);memcpy(&L->rlow, &Temp, sizeof(R

44、edType);return low;void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum) int PivotLoc = 0;if (low < high)PivotLoc = Partition(L, low, high, CmpNum, ChgNum);QSort(L, low, PivotLoc - 1, CmpNum, ChgNum);QSort(L, PivotLoc + 1, high, CmpNum, ChgNum);void QuickSort(LinkList *L, int *CmpN

45、um, int *ChgNum) QSort(L, 0, L->Length - 1, CmpNum, ChgNum);/堆排序void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int *ChgNum) RedType Temp;int j = 0;s+;memcpy(&Temp, &L->rs - 1, sizeof(RedType);for (j = 2 * s; j <= m; j *= 2)if (j < m && LT(L->rj - 1.key, L->

46、rj.key, CmpNum)+j;if (!LT(Temp.key, L->rj - 1.key, CmpNum)break;(*ChgNum)+;memcpy(&L->rs - 1, &L->rj - 1, sizeof(RedType);s = j;memcpy(&L->rs - 1, &Temp, sizeof(RedType);void HeapSort(LinkList *L, int *CmpNum, int *ChgNum)int i = 0;RedType Temp;for (i = L->Length / 2-1

47、; i >= 0; i-)HeapAdjust(L, i, L->Length, CmpNum, ChgNum);for (i = L->Length; i > 1; i-)memcpy(&Temp, &L->r0, sizeof(RedType);(*ChgNum)+;memcpy(&L->r0, &L->ri - 1, sizeof(RedType);memcpy(&L->ri - 1, &Temp, sizeof(RedType);HeapAdjust(L, 0, i - 1, CmpNum,

48、 ChgNum);/冒泡排序void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum) int i, j;RedType temp;for (i = 1; i <= MAXSIZE; i+)for (j = 1; j <= MAXSIZE - i; j+)if (!LT(L->rj.key, L->rj + 1.key, CmpNum)(*ChgNum)+;memcpy(&temp, &L->rj, sizeof(RedType);memcpy(&L->rj, &L->r

49、j + 1, sizeof(RedType);memcpy(&L->rj + 1, &temp, sizeof(RedType);/選擇排序int SelectMinKey(LinkList *L, int k, int *CmpNum)int Min = k;for (; k < L->Length; k+)if (!LT(L->rMin.key, L->rk.key, CmpNum)Min = k;return Min;void SelSort(LinkList *L, int *CmpNum, int *ChgNum)int i, j;Red

50、Type temp;for (i = 0; i < L->Length; i+)j = SelectMinKey(L, i, CmpNum);if (i != j)(*ChgNum)+;memcpy(&temp, &L->ri, sizeof(RedType);memcpy(&L->ri, &L->rj, sizeof(RedType);memcpy(&L->rj, &temp, sizeof(RedType);void SelectSort()printf("1.插入排序 n");prin

51、tf("2.希爾排序 n");printf("3.快速排序 n");printf("4.堆排序 n");printf("5.冒泡排序 n");printf("6.選擇排序n");printf("7.以上所有排序方式n");printf("8.退出程序 nn");printf("Please Select the Operate:");void AllAbove(LinkList *L, int *CmpNum, int *ChgNum)

52、int TempTime, i,j;int SpendTime;int dlta3 = 7, 3, 1；int Indata1 = 1；for (i = 1; i <= MAXSIZE; i+)L->ri.key = RandArrayi;/ 隨機(jī)數(shù)列復(fù)位printf("n插入排序:n");TempTime = (int)GetTickCount();ShellSort(L, Indata, 1, &CmpNum0, &ChgNum0);SpendTime = (int)GetTickCount() - TempTime;printf("nCompareNumber=%dtChageNumber=%dtTimeSpent=%dmsn",CmpNum0,ChgNum0,SpendTime); for (i = 1; i <= MAXSIZE; i+)L->ri.key = RandArrayi;/ 隨機(jī)數(shù)列復(fù)位printf("n 希爾排序：n");TempTime = (int)GetTickCount();ShellSort(L, dlta, 3, &Cmp