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

1、WORD格式標(biāo)準(zhǔn)*大學(xué)"數(shù)據(jù)構(gòu)造"課程設(shè)計(jì)報(bào)告專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)目 錄排序算法比較一、需求分析二、程序的主要功能三、程序運(yùn)行平臺(tái)四、數(shù)據(jù)構(gòu)造五、算法及時(shí)間復(fù)雜度六、測(cè)試用例七、程序源代碼二 感想體會(huì)與總結(jié)專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)排序算法比較一、需求分析利用隨機(jī)函數(shù)產(chǎn)生N 個(gè)隨機(jī)整數(shù) N = 500，1000，1500，2000，2500， ,30000，利用直接插入排序、折半插入排序，起泡排序、快速排序、選擇排序、堆排序，基數(shù)排序七種排序方法可添加其它排序方法進(jìn)展排序結(jié)果為由小到大的順序，并統(tǒng)計(jì)每一種排序

2、所消耗的時(shí)間統(tǒng)計(jì)為圖表坐標(biāo)形式。二、程序的主要功能1.用戶輸入任意個(gè)數(shù)，產(chǎn)生相應(yīng)的隨機(jī)數(shù)2.用戶可以自己選擇排序方式直接插入排序、折半插入排序、起泡排序、快速排序、選擇排序、堆排序、基數(shù)排序的一種3.程序給出原始數(shù)據(jù)、排序后從小到大的數(shù)據(jù)，并給出排序所用的時(shí)間。三、程序運(yùn)行平臺(tái)Visual C+6.0 版本四、數(shù)據(jù)構(gòu)造本程序的數(shù)據(jù)構(gòu)造為線形表，線性順序表、線性鏈表。1、構(gòu)造體：typedef structint*r; /r 指向線形表的第一個(gè)結(jié)點(diǎn)。r0 閑置，不同的算法有不同的用處，如用作哨兵等。intlength; /順序表的總長(zhǎng)度Sqlist;2、空線性表Status InitSqlist

3、(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int); /分配存儲(chǔ)空間 if(!L.r)printf(" 存儲(chǔ)分配失?。?");exit(0); /存儲(chǔ)分配失敗專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)L.length=0;/初始長(zhǎng)度為 0return OK;五、算法及時(shí)間復(fù)雜度一各個(gè)排序是算法思想：（ 1直接插入排序：將一個(gè)記錄插入到已排好的有序表中，從而得到一個(gè)新的，記錄數(shù)增加 1 的有序表。（ 2折半插入排序：插入排序的根本插入是在一個(gè)有序表中進(jìn)展查找和插入，這個(gè)查找可利用折半查找來實(shí)現(xiàn)，即為折半插入排

4、序。（ 3起泡排序：首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)展比較，假設(shè)為逆序，那么將兩個(gè)記錄交換，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。依此類推，直到第 N-1 和第 N個(gè)記錄的關(guān)鍵字進(jìn)展過比較為止。上述為第一趟排序，其結(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

5、個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第 I 1<=I<=N個(gè)記錄交換。（ 6堆排序：在堆排序的算法中先建一個(gè)大頂堆，既先選得一個(gè)關(guān)鍵字作為最大的記錄并與序列中最后一個(gè)記錄交換，然后對(duì)序列中前 N-1 記錄進(jìn)展選擇，重新將它調(diào)整成一個(gè)大頂堆，如此反復(fù)直到排序結(jié)束。（ 7基數(shù)排序：按最低位優(yōu)先法先對(duì)低位關(guān)鍵字進(jìn)展排序，直到對(duì)最高位關(guān)鍵字排序?yàn)橹?，?jīng)過假設(shè)干次分配和收集來實(shí)現(xiàn)排序二時(shí)間復(fù)雜度分析排序算法最差時(shí)間時(shí)間復(fù)雜度是否穩(wěn)定？插入排序O(n2)O(n2 )穩(wěn)定冒泡排序O(n2)O(n2 )穩(wěn)定專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)快速排序O(n2)O(n*log 2n

6、)不穩(wěn)定選擇排序O(n2)O(n2 )穩(wěn)定堆排序O(n*log 2n)O(n*log 2n)不穩(wěn)定基數(shù)排序O(n*log 2n)O(n2 )穩(wěn)定10000 個(gè)數(shù)據(jù)的時(shí)間比較：算法名稱用時(shí)直接插入排序0.25折半插入排序0.219起泡排序0.704快速排序0.016選擇排序0.39堆排序0.0001基數(shù)排序0.016六、測(cè)試用例1、首先選擇需要排序的數(shù)字個(gè)數(shù)，比方輸入5000。專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)2、系統(tǒng)顯示出隨機(jī)產(chǎn)生的隨機(jī)數(shù)。用戶選擇排序方式，比方選擇1.直接插入排序?qū)I(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)3、系統(tǒng)將隨機(jī)數(shù)排序后整齊的顯示出來

7、。4、用戶可以選擇繼續(xù)排序或者退出系統(tǒng)。七、程序源代碼/* 第六題：排序算法比較設(shè)計(jì)要求：利用隨機(jī)函數(shù)產(chǎn)生N 個(gè)隨機(jī)整數(shù) N = 500 ，1000 ，1500 ， 2000 ，2500 ， ,30000 ，專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)利用直接插入排序、折半插入排序，起泡排序、快速排序、 |選擇排序、堆排序，基數(shù)排序七種排序方法可添加其它排序方法進(jìn)展排序結(jié)果為由小到大的順序，并統(tǒng)計(jì)每一種排序所消耗的時(shí)間統(tǒng)計(jì)為圖表坐標(biāo)形式。*/#include "stdio.h"#include "stdlib.h"#include "

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

9、it(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ù)專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)printf("nn");printf("隨機(jī)產(chǎn)生了 %d 個(gè)隨機(jī)數(shù)，它們是：n&q

10、uot;,N);for(i=1;i<=N;i+)printf("%7.2d",L.ri);printf("n");L.length=N; / 存儲(chǔ)線性表的長(zhǎng)度return OK;/輸出排序之后的數(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+)

11、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.length;i+)if(L.ri<L.ri-1)/將 L.ri 插入有序子表L.r0=L.ri;/復(fù)制為監(jiān)視哨L.ri=L.ri-1;專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD

12、格式標(biāo)準(zhǔn)for(j=i-2;L.r0<L.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 暫存在 L.r0low=1;high=i-1;while(low<=hi

13、gh)/在 rlow.high 中折半查找有序插入的位置mid=(low+high)/2;if(L.r0<L.rmid)/ 插入點(diǎn)在低半?yún)^(qū)high=mid-1;elselow=mid+1;/插入點(diǎn)在高半?yún)^(qū)/whilefor(j=i-1;j>=high+1;j-)/插入點(diǎn)后的數(shù)據(jù)后移L.rj+1=L.rj;L.rhigh+1=L.r0;/將數(shù)據(jù)插入專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)/forreturn OK;/*希爾排序*/參考書 P272 算法 10.4 及 10.5/*Status ShellInsert(Sqlist &L,int dk)/希爾插入

14、排序int i,j;/前后位置的增量是dkfor(i=dk+1;i<=L.length;i+)/r0 只是暫存單元，不是哨兵，if(L.ri<L.ri-dk)/將 L.ri 插入有序增量子表L.r0=L.ri;/暫存 L.r0for(j=i-dk;j>0 && L.r0<L.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(&q

15、uot; 要排序的數(shù)據(jù)為空！");return ERROR;for(i=0;i<t;i+)ShellInsert(L,dltai);/一趟增量為 dltak 的插入排序?qū)I(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)return OK;*/*/起泡排序/*Status BubbleSort(Sqlist &L)int i,j,t;if(L.length=0)printf(" 要排序的數(shù)據(jù)為空！");return ERROR;for(i=1;i<=L.length-1;i+)for(j=1;j<=L.length-i;j+)if(L

16、.rj>L.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;/用樞軸紀(jì)錄關(guān)鍵字while (low<high)while(low<high

17、&& L.rhigh>=pivotkey)專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)high-;L.rlow= L.rhigh;/將比樞軸記錄小的記錄移到低端while(low<high && 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(low<high)/長(zhǎng)度大

18、于 1，可以進(jìn)展pivotloc=Partition(L, low ,high);Qsort(L,low,pivotloc-1);/對(duì)低子表遞歸排序，pivotloc 是樞軸位置Qsort(L,pivotloc+1,high);/ 對(duì)高子表遞歸排序/Qsort 函數(shù)StatusQuickSort (Sqlist &L)if(L.length=0)printf(" 要排序的數(shù)據(jù)為空！");return ERROR;Qsort(L,1,L.length);return OK;/QuickSort/*/選擇排序/*Status ChooseSort(Sqlist &

19、;L)int i,j,k,t;if(L.length=0)printf(" 沒有數(shù)據(jù)！ ");return ERROR;專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)for(i=1;i<=L.length;i+)/排序的趟數(shù)k=i;for(j=i+1;j<=L.length;j+)/比較第 i 個(gè)元素以及其后的數(shù)據(jù)中最小的if(L.rj<L.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,in

20、t 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(i<m && L.ri<L.ri+1)/i 為數(shù)據(jù)較大的記錄下標(biāo)i+;if(L.r0>=L.ri)/L.r0 插入在 S 位置上break;L.rs=L.ri;s=i;L.rs=L.r0;/插入新數(shù)據(jù)return OK;Status HeapSort(Sqlist &L)/堆排序int i,t;專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)if(L.le

21、ngth=0)printf(" 沒有數(shù)據(jù)！ ");return ERROR;for(i=L.length/2;i>0;i-)HeapAdjust(L,i,L.length);for(i=L.length;i>1;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)整為大頂堆return OK;/*/基數(shù)排序/*typedef struct nodeintkey;node *next;RecType;StatusRadixSor

22、t(Sqlist L)int t,i,j,k,d,n=1,m;RecType *p,*s,*q,*head10,*tail10;/定義各鏈隊(duì)的首尾指針for(i=1;i<=L.length;i+)/ 將順序表轉(zhuǎn)化為鏈表s=(RecType*)malloc(sizeof(RecType);s->key=L.ri;if(i=1) / 當(dāng)為第一個(gè)元素時(shí)q=s;p=s;t+;elseq->next=s; /將鏈表連接起來q=s;t+;專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)q->next=NULL;d=1;while(n>0)/將每個(gè)元素分配至各個(gè)鏈隊(duì)fo

23、r(j=0;j<10;j+)/初始化各鏈隊(duì)首、尾指針headj = NULL;tailj = NULL;while(p!=NULL)/對(duì)于原鏈表中的每個(gè)結(jié)點(diǎn)循環(huán)k=p->key/d;k=k%10;if(headk=NULL)/進(jìn)展分配headk=p;tailk=p;elsetailk->next=p;tailk=p;p=p->next;/取下一個(gè)待排序的元素p=NULL;/用于收集第一個(gè)元素時(shí)的判斷for(j=0;j<10;j+)/對(duì)每一個(gè)鏈隊(duì)循環(huán)，搜集每一個(gè)元素if(headj!=NULL)/ 進(jìn)展搜集if(p=NULL)p=headj;q=tailj;else

24、q->next=headj;q=tailj;q->next=NULL;/最后一個(gè)結(jié)點(diǎn)的next 置為空d=d*10;專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)n=0;m=1;while(m<=L.length)/ 判斷當(dāng) L 中的元素都除d 后是不是都為零了if(L.rm/d)!=0)n+;m+;elsem+;i=1;while(p!=NULL) /將鏈表轉(zhuǎn)換為順序表L.ri=p->key;i+;p=p->next;return OK;/*/主函數(shù)/*void main()Sqlist L;Sqlist L0;InitSqlist(L);/初始化 L

25、InitSqlist(L0);int m,i;char choice='z'clock_t start, finish; /定義 clock_t 用于計(jì)時(shí)double duration;/向 L 中輸入元素n n");printf("n");printf("算法排序比較系統(tǒng)n");printf("n");printf("n");專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)printf("以下是各個(gè)排序算法的代號(hào)：nn");printf("1、直接插

26、入排序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");ScanfSqlist(m,L0);printf("n");printf("1、直接插入排序n");printf("

27、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(ch

28、oice<1|choice>8)printf(" 輸入方式有誤。 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(

29、);BInsertSort(L);finish = clock();專業(yè)資料整理WORD格式文案專業(yè)資料整理WORD格式標(biāo)準(zhǔn)break;case 3:/ 起泡排序start = clock();BubbleSort(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í)間是：%lf secondsn",duration);printf("本次排序完畢。 n&q