1、攀 枝 花 學(xué) 院 實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)課程：計(jì)算機(jī)算法實(shí)驗(yàn) 實(shí)驗(yàn)項(xiàng)目：比較多種不同排序算法 實(shí)驗(yàn)日期：2013.3.26系：數(shù)學(xué)與計(jì)算機(jī)學(xué)院 班級(jí)：軟件工程 姓名：馮斌 學(xué)號(hào)：4指導(dǎo)教師：銀星 成績(jī)： 【實(shí)驗(yàn)?zāi)康模骸?. 掌握基本的排序算法2. 學(xué)習(xí)各種算法實(shí)現(xiàn)的優(yōu)劣3. 掌握vc+6.0環(huán)境下程序的編寫和調(diào)試【實(shí)驗(yàn)設(shè)備器材：】1. pc機(jī)一套2. java相應(yīng)編譯軟件【實(shí)驗(yàn)原理：】基于直接插入，折半插入排序，冒泡排序，快速排序的實(shí)現(xiàn)，并記錄其實(shí)現(xiàn)所用比較次數(shù)?！緦?shí)驗(yàn)內(nèi)容：】1. 編寫相應(yīng)算法源程序2. 在vc+6.0環(huán)境下調(diào)試通過3. 通過程序排序所交換的次數(shù)，比較各種算法的優(yōu)劣程序代碼如下

2、：#include #include #include #define Recordtype intvoid copy(Recordtype s, Recordtype d, int n);/*/* 直接插入法 */*/int cmpTforIs = 0;/記錄插入法的比較次數(shù)int ChgTforIs = 0;/記錄插入法的交換次數(shù)void InsertSort(Recordtype data, int n);/*/* 折半插入法 */*/int cmpTforBinarys = 0;/記錄冒泡的比較次數(shù)int ChgTforBinarys = 0;/記錄冒泡的交換次數(shù)void Binary

3、SearchInsertion(int numbers, const int n);/*/* 冒泡法 */*/int cmpTforBs = 0;/記錄冒泡的比較次數(shù)int ChgTforBs = 0;/記錄冒泡的交換次數(shù)void Bubsort(Recordtype *start, Recordtype *end);/*/* 快排 */*/int cmpTforQs = 0;/記錄快排的比較次數(shù)int ChgTforQs = 0;/記錄快排的交換次數(shù)int quickPass(int start, int last, Recordtype record);int quickSort(int

4、start, int last, Recordtype record);int main()Recordtype Data100;Recordtype D100;srand(time(NULL);printf(the rand 100 numbers are:n);for (int i=0; i100; i+)Di = rand()%1000;/便于觀察,每次產(chǎn)生1000內(nèi)的整數(shù)printf(%d , Di);printf(nnn);copy(D, Data, 100);BinarySearchInsertion(Data, 100);printf(折半插入法的比較次數(shù)為%d,交換次數(shù)為%dn

5、, cmpTforBinarys, ChgTforBinarys);copy(D, Data, 100); InsertSort(Data, 100); printf(直接插入法的比較次數(shù)為%d,交換次數(shù)為%dn, cmpTforIs, ChgTforIs);copy(D, Data, 100); Bubsort(&Data0, &Data99); printf(冒泡法的比較次數(shù)為%d,交換次數(shù)為%dn, cmpTforBs, ChgTforBs);copy(D, Data, 100);quickSort(0, 99, Data);printf(快排的比較次數(shù)為%d,交換次數(shù)為%dn, cmp

6、TforQs, ChgTforQs);printf(排序后的序列為n);/你可以這塊放在任意排序完畢的語句后面,檢查排序的正確性 for (i=0; i100; i+)printf(%d , Datai);return 0;void copy(Recordtype s, Recordtype d, int n)for (int i = 0; in; i+)di = si;void BinarySearchInsertion(int numbers, const int n) int middle=0; for(int i = 1; i n; i+) int low = 0 ; int high

7、 = i-1 ; int temp = numbersi ; while(low = high) cmpTforBinarys+;middle = (low + high) / 2 ; if(temp middle; k-) ChgTforBinarys+;numbersk = numbersk-1 ;ChgTforBinarys+;numberslow = temp ; void InsertSort(Recordtype data, int n)for (int i = 1; i0 & tempdataj-1; -j)ChgTforIs+;cmpTforIs+;dataj = dataj-

8、1;dataj =temp;void Bubsort(Recordtype *start, Recordtype *end)int num = end - start + 1;Recordtype temp;int i, j;Recordtype *a = start;for (i = 0; inum; i+)for (j = 0; j *(a+j)ChgTforBs+;temp = *(a+j-1);*(a+j-1) = *(a+j);*(a+j) = temp;int quickPass(int start, int last, Recordtype record)int s = star

9、t, l = last;int temp = records;while (s l)while (sl & temp = recordl )l-;cmpTforQs+;if (sl)records+ = recordl;ChgTforQs+;while (s= records)s+;cmpTforQs+;if (sl)recordl- = records;ChgTforQs+;records = temp;ChgTforQs+;return s;int quickSort(int start, int last, Recordtype record)int pos = 0;if (start

10、last)pos = quickPass(start, last, record);quickSort(start, pos-1, record);quickSort(pos+1, last, record);return 0;#include#include#define MAXSIZE 20#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define LQ(a,b) (a)=(b)#define N 7typedef int KeyType;typedef int InfoType; /* 定義其它數(shù)據(jù)項(xiàng)的類型 */typedef struct

11、KeyType key; /* 關(guān)鍵字項(xiàng) */ InfoType otherinfo; /* 其它數(shù)據(jù)項(xiàng)，具體類型在主程中定義 */ RedType; /* 記錄類型 */ typedef struct RedType rMAXSIZE+1; /* r0閑置或用作哨兵單元 */ int length; /* 順序表長(zhǎng)度 */ SqList; /* 順序表類型 */ void Merge(RedType SR,RedType TR,int i,int m,int n) /* 將有序的SRi.m和SRm+1.n歸并為有序的TRi.n 算法10.12 */ int j,k,l; for(j=m+1,

12、k=i;i=m&j=n;+k) /* 將SR中記錄由小到大地并入TR */ if LQ(SRi.key,SRj.key) TRk=SRi+; else TRk=SRj+; if(i=m) for(l=0;l=m-i;l+) TRk+l=SRi+l; /* 將剩余的SRi.m復(fù)制到TR */ if(j=n) for(l=0;l=n-j;l+) TRk+l=SRj+l; /* 將剩余的SRj.n復(fù)制到TR */ void MSort(RedType SR,RedType TR1,int s, int t) /* 將SRs.t歸并排序?yàn)門R1s.t。算法10.13 */ int m; RedType

13、 TR2MAXSIZE+1; if(s=t) TR1s=SRs; else m=(s+t)/2; /* 將SRs.t平分為SRs.m和SRm+1.t */ MSort(SR,TR2,s,m); /* 遞歸地將SRs.m歸并為有序的TR2s.m */ MSort(SR,TR2,m+1,t); /* 遞歸地將SRm+1.t歸并為有序的TR2m+1.t */ Merge(TR2,TR1,s,m,t); /* 將TR2s.m和TR2m+1.t歸并到TR1s.t */ void MergeSort(SqList *L) /* 對(duì)順序表L作歸并排序。算法10.14 */ MSort(*L).r,(*L).r,1,(*L).length); void print(SqList L) int i; for(i=1;i=L.