數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)_排序算法比較【完整版

1、XXXXXX大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告目 錄排序算法比較1、 需求分析2、 程序的主要功能3、 程序運(yùn)行平臺(tái)4、 數(shù)據(jù)結(jié)構(gòu)5、 算法及時(shí)間復(fù)雜度6、 測(cè)試用例7、 程序源代碼二 感想體會(huì)與總結(jié)排序算法比較一、需求分析利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（N = 500，1000，1500，2000，2500，,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、選擇排序、堆排序，基數(shù)排序七種排序方法（可添加其它排序方法）進(jìn)行排序（結(jié)果為由小到大的順序），并統(tǒng)計(jì)每一種排序所耗費(fèi)的時(shí)間（統(tǒng)計(jì)為圖表坐標(biāo)形式）。二、程序的主要功能1.用戶輸入任意個(gè)數(shù)，產(chǎn)生相應(yīng)的隨機(jī)數(shù)2.用戶可以自己選擇排序方式（

2、直接插入排序、折半插入排序、起泡排序、快速排序、選擇排序、堆排序、基數(shù)排序）的一種3.程序給出原始數(shù)據(jù)、排序后從小到大的數(shù)據(jù)，并給出排序所用的時(shí)間。三、程序運(yùn)行平臺(tái)Visual C+ 6.0版本四、數(shù)據(jù)結(jié)構(gòu)本程序的數(shù)據(jù)結(jié)構(gòu)為線形表，線性順序表、線性鏈表。1、結(jié)構(gòu)體： typedef struct int *r; /r指向線形表的第一個(gè)結(jié)點(diǎn)。 r0閑置，不同的算法有不同的用處，如用作哨兵等。 int length; /順序表的總長(zhǎng)度Sqlist;2、空線性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int); /分配

3、存儲(chǔ)空間if(!L.r) printf(存儲(chǔ)分配失??！);exit(0); /存儲(chǔ)分配失敗L.length=0;/初始長(zhǎng)度為0return OK;五、算法及時(shí)間復(fù)雜度（一）各個(gè)排序是算法思想：（1）直接插入排序：將一個(gè)記錄插入到已排好的有序表中，從而得到一個(gè)新的，記錄數(shù)增加1的有序表。（2）折半插入排序：插入排序的基本插入是在一個(gè)有序表中進(jìn)行查找和插入，這個(gè)查找可利用折半查找來實(shí)現(xiàn)，即為折半插入排序。（3）起泡排序：首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。依此類推，直到第N-1和第N個(gè)記錄的關(guān)鍵字進(jìn)行過比較為止。

4、上述為第一趟排序，其結(jié)果使得關(guān)鍵字的最大紀(jì)錄被安排到最后一個(gè)記錄的位置上。然后進(jìn)行第二趟起泡排序，對(duì)前N-1個(gè)記錄進(jìn)行同樣操作。一共要進(jìn)行N-1趟起泡排序。（4）快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，已達(dá)到整個(gè)序列有序。（5）選擇排序：通過N-I次關(guān)鍵字間的比較，從N-I+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第I（1=I=N）個(gè)記錄交換。（6）堆排序：在堆排序的算法中先建一個(gè)大頂堆，既先選得一個(gè)關(guān)鍵字作為最大的記錄并與序列中最后一個(gè)記錄交換，然后對(duì)序列中前N-1記錄進(jìn)行選擇，重新將它調(diào)整成一個(gè)大

5、頂堆，如此反復(fù)直到排序結(jié)束。（7）基數(shù)排序：按最低位優(yōu)先法先對(duì)低位關(guān)鍵字進(jìn)行排序，直到對(duì)最高位關(guān)鍵字排序?yàn)橹?，?jīng)過若干次分配和收集來實(shí)現(xiàn)排序（二）時(shí)間復(fù)雜度分析排序算法 最差時(shí)間時(shí)間復(fù)雜度 是否穩(wěn)定？插入排序 O(n2)O(n2) 穩(wěn)定 冒泡排序O(n2)O(n2) 穩(wěn)定 快速排序O(n2)O(n*log2n) 不穩(wěn)定 選擇排序O(n2)O(n2) 穩(wěn)定 堆排序O(n*log2n) O(n*log2n) 不穩(wěn)定 基數(shù)排序O(n*log2n)O(n2)穩(wěn)定10000個(gè)數(shù)據(jù)的時(shí)間比較：算法名稱用時(shí)直接插入排序0.25折半插入排序0.219起泡排序0.704快速排序0.016選擇排序0.39堆排序0

6、.0001基數(shù)排序0.016六、測(cè)試用例1、首先選擇需要排序的數(shù)字個(gè)數(shù)，比如輸入5000。2、系統(tǒng)顯示出隨機(jī)產(chǎn)生的隨機(jī)數(shù)。 用戶選擇排序方式，比如選擇1.直接插入排序3、 系統(tǒng)將隨機(jī)數(shù)排序后整齊的顯示出來。4、 用戶可以選擇繼續(xù)排序或者退出系統(tǒng)。七、程序源代碼/*第六題：排序算法比較設(shè)計(jì)要求：利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（N = 500，1000，1500，2000，2500，,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、|選擇排序、堆排序，基數(shù)排序七種排序方法（可添加其它排序方法）進(jìn)行排序（結(jié)果為由小到大的順序），并統(tǒng)計(jì)每一種排序所耗費(fèi)的時(shí)間（統(tǒng)計(jì)為圖表坐標(biāo)形式）。*/

7、#include stdio.h#include stdlib.h#include time.h/計(jì)時(shí)#define ERROR 0#define OK 1#define OVERFLOW -2#define MAXSIZE /用戶自己規(guī)定排序的數(shù)字的長(zhǎng)度typedef int Status;typedef struct int *r; / r0閑置 int length; /順序表的總長(zhǎng)度Sqlist;/構(gòu)造一個(gè)空線性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int); /分配存儲(chǔ)空間if(!L.r) prin

8、tf(存儲(chǔ)分配失??！);exit(0); /存儲(chǔ)分配失敗L.length=0;/初始長(zhǎng)度為0return OK;/輸入隨機(jī)數(shù)并顯示在界面上Status ScanfSqlist(int &N,Sqlist &L)int i;printf(請(qǐng)輸入要排序的元素個(gè)數(shù)N: );scanf(%d,&N);for(i=1;i=N;i+)L.ri=rand(); /隨機(jī)產(chǎn)生樣本整數(shù)printf(nn);printf( 隨機(jī)產(chǎn)生了%d個(gè)隨機(jī)數(shù)，它們是：n,N);for(i=1;i=N;i+)printf(%7.2d ,L.ri);printf(n);L.length=N; /存儲(chǔ)線性表的長(zhǎng)度return OK;

9、/輸出排序之后的數(shù)據(jù)Status PrintfSqlist(int N,Sqlist L)int i;printf(數(shù)據(jù)個(gè)數(shù)：);/輸出數(shù)據(jù)個(gè)數(shù)printf(%dn,L.length);printf(排序后的數(shù)據(jù)：(從左向右依次增大)n);/輸出數(shù)據(jù)for(i=1;i=N;i+)printf(%7.2d ,L.ri);printf(n); return OK;/*/ 直接插入排序/*Status InsertSort(Sqlist &L)/參考書P265算法10.1int i,j;if(L.length=0)printf(要排序的數(shù)據(jù)為空！);return ERROR;for(i=2;i=L.

10、length;i+)if(L.riL.ri-1) /將L.ri插入有序子表L.r0=L.ri; /復(fù)制為監(jiān)視哨L.ri=L.ri-1; for(j=i-2;L.r0L.rj;j-)L.rj+1=L.rj; /記錄后移L.rj+1=L.r0; /插入到正確位置return OK;/*/ 折半插入排序/*Status BInsertSort(Sqlist &L) /參考書P267算法10.2int i,j,mid,low,high;if(L.length=0)printf(要排序的數(shù)據(jù)為空！);return ERROR;for(i=2;i=L.length;i+)L.r0=L.ri; /將L.ri

11、暫存在L.r0low=1;high=i-1;while(low=high) /在rlow.high中折半查找有序插入的位置mid=(low+high)/2;if(L.r0=high+1;j-) /插入點(diǎn)后的數(shù)據(jù)后移L.rj+1=L.rj; L.rhigh+1=L.r0; /將數(shù)據(jù)插入/forreturn OK;/* 希爾排序*/ /參考書P272算法10.4及10.5/*Status ShellInsert(Sqlist &L,int dk)/希爾插入排序 int i,j;/前后位置的增量是dkfor(i=dk+1;i=L.length;i+)/r0只是暫存單元，不是哨兵，if(L.ri0 &

12、 L.r0L.rj;j-=dk)L.rj+dk=L.rj;/記錄后移,查找插入位置L.rj+dk=L.r0;/插入return OK;Status ShellSort(Sqlist &L,int dlta5,int t) /希爾排序 int i;if(L.length=0)printf(要排序的數(shù)據(jù)為空！);return ERROR;for(i=0;it;i+)ShellInsert(L,dltai);/一趟增量為dltak的插入排序return OK;*/*/ 起泡排序/*Status BubbleSort(Sqlist &L)int i,j,t;if(L.length=0)printf(要

13、排序的數(shù)據(jù)為空！);return ERROR;for(i=1;i=L.length-1;i+)for(j=1;jL.rj+1) /前面的數(shù)據(jù)后面數(shù)據(jù)時(shí)t=L.rj+1;L.rj+1=L.rj;L.rj=t; /將元素交換return OK;/*/ 快速排序/*int Partition(Sqlist &L, int low, int high) /交換順序表中子表L.rlow.high的記錄，使得樞軸記錄到位，并返回其所在位置，此時(shí)在它之前（后）的記錄均不大于它int pivotkey; /記錄關(guān)鍵字L.r0=L.rlow; /用子表的第一個(gè)紀(jì)錄作樞軸紀(jì)錄 pivotkey=L.rlow; /

14、用樞軸紀(jì)錄關(guān)鍵字 while (lowhigh) while(low=pivotkey) high-;L.rlow= L.rhigh; /將比樞軸記錄小的記錄移到低端while(lowhigh & L.rlow=pivotkey) low+;L.rhigh=L.rlow; /將比樞軸記錄大的數(shù)移到高端 L.rlow=L.r0; /樞軸記錄到位 return low;/Partition函數(shù)void Qsort (Sqlist &L,int low, int high) int pivotloc;if (lowhigh) /長(zhǎng)度大于1，可以進(jìn)行 pivotloc=Partition(L, low

15、 ,high);Qsort(L,low,pivotloc-1); /對(duì)低子表遞歸排序，pivotloc是樞軸位置Qsort(L,pivotloc+1,high); /對(duì)高子表遞歸排序/Qsort函數(shù)Status QuickSort (Sqlist &L) if(L.length=0)printf(要排序的數(shù)據(jù)為空！);return ERROR;Qsort(L,1,L.length);return OK;/QuickSort/*/ 選擇排序/*Status ChooseSort(Sqlist &L)int i,j,k,t;if(L.length=0)printf(沒有數(shù)據(jù)！);return ER

16、ROR;for(i=1;i=L.length;i+) /排序的趟數(shù)k=i;for(j=i+1;j=L.length;j+) /比較第i個(gè)元素以及其后的數(shù)據(jù)中最小的 if(L.rjL.rk)k=j;if(i!=j) /將最小數(shù)據(jù)賦值給L.rit=L.ri;L.ri=L.rk;L.rk=t;return OK;/*/ 堆排序/*Status HeapAdjust(Sqlist &L,int s,int m) /調(diào)整L.rs的關(guān)鍵字,使L.rsm成大頂堆int i;L.r0=L.rs;for(i=2*s;i+1=m;i*=2) /沿?cái)?shù)據(jù)較大的孩子結(jié)點(diǎn)向下篩選if(im & L.ri=L.ri) /L

17、.r0插入在S位置上break;L.rs=L.ri;s=i;L.rs=L.r0; /插入新數(shù)據(jù) return OK;Status HeapSort(Sqlist &L) /堆排序int i,t;if(L.length=0)printf(沒有數(shù)據(jù)！);return ERROR;for(i=L.length/2;i0;i-)HeapAdjust(L,i,L.length);for(i=L.length;i1;i-)t=L.r1; /將堆頂記錄和當(dāng)前未經(jīng)排序的子序列L.r1.i中最后一個(gè)記錄互換L.r1=L.ri;L.ri=t;HeapAdjust(L,1,i-1); /將L.r1.i-1重新調(diào)整為

18、大頂堆return OK;/*/ 基數(shù)排序/*typedef struct node int key; node *next; RecType; Status RadixSort(Sqlist L) int t,i,j,k,d,n=1,m; RecType *p,*s,*q,*head10,*tail10; /定義各鏈隊(duì)的首尾指針 for(i=1;ikey=L.ri; if(i=1) /當(dāng)為第一個(gè)元素時(shí) q=s; p=s; t+; else q-next=s; /將鏈表連接起來q=s; t+; q-next=NULL; d=1;while(n0) /將每個(gè)元素分配至各個(gè)鏈隊(duì)for(j=0;jk

19、ey/d; k=k%10; if(headk=NULL) /進(jìn)行分配 headk=p; tailk=p; else tailk-next=p; tailk=p; p=p-next; /取下一個(gè)待排序的元素 p=NULL; /用于收集第一個(gè)元素時(shí)的判斷for(j=0;jnext=headj; q=tailj; q-next=NULL; /最后一個(gè)結(jié)點(diǎn)的next置為空 d=d*10; n=0;m=1;while(mkey; i+; p=p-next;return OK;/*/ 主函數(shù)/*void main()Sqlist L;Sqlist L0;InitSqlist(L); /初始化LInitSq

20、list(L0); int m,i; char choice=z;clock_t start, finish; /定義clock_t用于計(jì)時(shí)double duration; /向L中輸入元素printf(n n);printf( n);printf( 算法排序比較系統(tǒng) n);printf( n);printf( n); printf( 以下是各個(gè)排序算法的代號(hào)：nn);printf( 1、直接插入排序 n);printf( 2、折半插入排序 n);printf( 3、起泡排序 n);printf( 4、快速排序n);printf( 5、選擇排序n);printf( 6、堆排序n);printf

21、( 7、基數(shù)排序n); printf( 8、退出該系統(tǒng)nn);ScanfSqlist(m,L0);printf(n);printf( 1、直接插入排序 n);printf( 2、折半插入排序 n);printf( 3、起泡排序 n);printf( 4、快速排序n);printf( 5、選擇排序n);printf( 6、堆排序n);printf( 7、基數(shù)排序n); printf( 8、退出該系統(tǒng)nn);printf(n請(qǐng)選擇排序的方式,數(shù)字1-7: );scanf(%d,&choice); /選擇排序方式賦值choice，用于后面的函數(shù)選擇while(choice8)printf(輸入方式有

22、誤。n請(qǐng)輸入1-7選擇排序方式，或者選擇8退出系統(tǒng));scanf(%d,&choice);while(choice!=8)for(i=1;i=L0.length;i+)L.ri=L0.ri;L.length=L0.length;switch(choice)case 1:/直接插入排序start = clock(); InsertSort(L);finish = clock();break;case 2:/折半插入排序start = clock();BInsertSort(L); finish = clock(); break;case 3:/起泡排序start = clock();Bubble

23、Sort(L);finish = clock(); break;case 4:/快速排序start = clock();QuickSort(L); finish = clock(); break;case 5:/選擇排序start = clock();ChooseSort(L);finish = clock(); break;case 6:/堆排序start = clock();HeapSort(L);finish = clock(); break;case 7:/基數(shù)排序start = clock();RadixSort(L);finish = clock(); break;case 8:/直接退出break;PrintfSqlist(m,L); /輸出數(shù)據(jù)和L的長(zhǎng)度duration = (double)(finish - start) / CLOCKS_PER_SEC; /輸出算術(shù)時(shí)間printf(n本次排序運(yùn)算所用的時(shí)間是