數(shù)據(jù)結(jié)構(gòu)與算法課程設計報告-內(nèi)部排序算法比較

課程設計報告課程數(shù)據(jù)結(jié)構(gòu)與算法課程設計名稱內(nèi)部排序算法比較題目：內(nèi)部排序算法比較在教科書中，各種內(nèi)部排序算法的時間復雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機數(shù)據(jù)比較各種算法的關鍵字比較次數(shù)和關鍵字移動次數(shù)，以取得直觀感受。 對以下7種常用的內(nèi)部排序算法進行比較：冒泡排序、直接插入排序、簡單選擇排序、希爾排序、堆排序、歸并排序、快速排序。待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機數(shù)程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標為有關鍵字參加的比較次數(shù)和關鍵字的移動次數(shù)（關鍵字交換計為3次移動）。最后要對結(jié)果作出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小的解釋。由隨機數(shù)產(chǎn)生器生成一、問題分析和任務定義：在本次課程設計中，正如前面所說的一樣，迫切需要一個能實現(xiàn)常用的排序算法，并對各種排序算法僅僅考慮在相同條件情況下直觀地反映排序算法在對比次數(shù)、移動次數(shù)、時間消耗方面的性能對比。本程序只做排序性能的分析，故人機交換方面要求不高，相關控制用宏實現(xiàn)。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設計：（一）數(shù)據(jù)結(jié)構(gòu)的選擇：（根據(jù)實驗的要求）//***結(jié)構(gòu)體***typedefstruct{KeyTypekey;}RedType;typedefstruct{ RedTyper[MAXSIZE+1]; intlength; intinfo;//記錄關鍵字移動次數(shù) intcmp;//關鍵字的比較次數(shù)}SqList;（二）概要設計：設計思路：首先，從完成的功能上看，用隨機種子產(chǎn)生隨機數(shù)（用時間），200取余，取100個數(shù)，對這100個數(shù)進行排序。三、詳細設計和編碼：//***冒泡排序***voidBubbleSort(SqList*L){ inti=0,j=0,k=0,change; intn=L->length,x; change=1;//記錄元素交換的標志變量for(i=0;i<n-1&&change;++i) { change=0; for(j=0;j<n-i-1;++j) {if(L->r[j].key>L->r[j+1].key)//如果前面的數(shù)大于后面的數(shù)就交換（從小到大排序） { x=L->r[j].key; L->r[j].key=L->r[j+1].key; L->r[j+1].key=x; L->info+=3;//由于進行三次交換關鍵字移動的次數(shù)為三次 change=1; } L->cmp++;//每經(jīng)過一次循環(huán)就會比較一次 } }}//***直接插入排序***voidInsertSort(SqList*L){ inti,j; RedTypek;//監(jiān)視哨 for(i=1;i<L->length;i++) { k=L->r[i];//將帶插入元素存到監(jiān)視哨中L->cmp++; j=i-1; while(k.key<L->r[j].key)//尋找插入位置 { L->r[j+1]=L->r[j]; L->info++; L->cmp++; j=j-1; } L->r[j+1]=k;//將待插入元素插入到已排序的的序列中L->cmp++; L->info++; }}//***簡單選擇排序***voidSelectSort(SqList*L){intn,i,k,j; n=L->length-1; for(i=0;i<n;i++) { for(j=i+1;j<n+1;j++) { if(L->r[j].key<L->r[i].key) { change(&L->r[j].key,&L->r[i].key);L->info+=3; }L->cmp++; } }}//***希爾排序***voidShellinsert(SqList*L,intdelta){//直接插入排序 inti,j,k,count=0; RedTypeflag; for(i=0;i<delta;i++) { for(j=i+delta;j<=L->length-1;j=j+delta) { flag.key=L->r[j].key; L->info++; k=j-delta; while((flag.key<L->r[k].key)&&k>=0) { L->r[k+delta].key=L->r[k].key; k=k-delta; L->cmp++;count=1; L->info++; } if(count==0)//防止多加了 { L->cmp++; } L->r[k+delta].key=flag.key; L->info++; count=0;//初始化count } }}SqList*ShellSort(SqList*L){ inti,di[100]; di[0]=L->length/2;//取長度的一半作為步長 for(i=0;i<L->length-1;i++) { Shellinsert(L,di[i]); di[i+1]=di[i]/2;//每次取其一半作為步長 if(di[i]==1)//當步長為1時，此時排序已結(jié)束序列已有序 { break;//跳出for循環(huán) } } returnL;}//***堆排序***voidSift(SqList*L,inti,intm){ intk,t; t=L->r[i].key;L->info++;k=2*i+1; while(k<m) { if((k<m-1)&&(L->r[k].key<L->r[k+1].key)) { k++; } if(t<L->r[k].key) { L->r[i].key=L->r[k].key; L->info++; i=k; k=2*i+1; } else { break; } L->cmp++; } L->r[i].key=t;L->info++;}voidHeapSort(SqList*L){ intn,i; RedTypetemp; n=L->length; for(i=n/2-1;i>=0;--i) { Sift(L,i,n); } for(i=n-1;i>=1;i--) { change(&L->r[0].key,&L->r[i].key); Sift(L,0,i); }}//***歸并排序***SqList*mergesort(SqList*L){ inti,di[100],flag=0,n; di[0]=2; n=L->length; for(i=0;i<L->length-1;i++) { merge(L,di[i]); di[i+1]=di[i]*2; if((di[i+1]>L->length)&&(di[i]<=L->length))//當步長小于等于順序表的長度時，步長*2大于順序表時，此時做最后的排序 { di[i]=n; merge(L,di[i]);//此時步長等于順序表的長度 break;//跳出for循環(huán) } } returnL;}voidmerge(SqList*L,intdelta){//用的是直接插入進行排序的 inti,j,k,n,count=0;; RedTypeflag; n=L->length-1;for(i=0;i<=n;i=i+delta) {for(j=i+1;((j<i+delta)&&(j<=n));j++) { flag.key=L->r[j].key; L->info++; k=j-1; while((flag.key<L->r[k].key)&&(k>=i)) { L->r[k+1].key=L->r[k].key; k=k-1; count=1;L->info++; L->cmp++; } if(count==0) { L->cmp++; } L->r[k+1].key=flag.key; L->info++; count=0; } }}//***快速排序***intPartition(SqList*H,intleft,intright){RedTypex; intlow,high,flag=0; x=H->r[left]; low=left; high=right; // printf("0"); while(low<high) { while(H->r[high].key>=x.key&&low<high) { high--; flag=1; H->cmp++; } if(low<high) { H->r[low]=H->r[high]; H->info++; low++; } while(H->r[low].key<x.key&&low<high) { if(flag==0) { H->cmp++; } low++; } if(low<high) { H->r[high]=H->r[low]; H->info++; high--; } if(flag==0) {H->cmp++;} } H->r[low]=x; H->info++; returnlow;}voidQuickSort(SqList*L,intlow,inthigh){ intmid; // printf("1"); if(low<high) { mid=Partition(L,low,high);QuickSort(L,low,mid-1); QuickSort(L,mid+1,high); }}四、測試結(jié)果及分析：五、測試結(jié)果及其分析表中數(shù)據(jù)為關鍵字移動次數(shù)：BubbleSortInsertSortSelectSortShellSortHeapSortmergesortQuickSort第一組69096906634514007943499288第二組75487548656113717753712295第三組68586858638713377903482271第四組79927992701713937783860293第五組75937593616214617773727309第六組76057605653114107653731304表中數(shù)據(jù)為關鍵字比較次數(shù)：BubbleSortInsertSortSelectSortShellSortHeapSortmergesortQuickSort第一組4872487249506754962641404第二組4935493549506484772872435第三組4949494949506224922630385第四組4922492249506594803008375第五組4719471949507294792877385第六組4872487249506784672889319有數(shù)據(jù)分析可知：無論待排序列排序如何，BubbleSort與SelectSort兩種算法的關鍵字比較次數(shù)均為4950，即n(n-1)/2次，待排序列偽隨機序列是直接插入排序的關鍵字比較次數(shù)和關鍵字移動平均值約為/4，正序時比較次數(shù)為(n-1),移動次數(shù)為0，逆序時為n(n-1)/2次；整體看來六種排序中QuickSort、ShellSort、HeapSort三種排序比較和移動次數(shù)相對較少；但BubbleSort、insertSort兩種屬于穩(wěn)定排序。在測試過程中，當連續(xù)選擇一個操作時，發(fā)現(xiàn)有的排序方式的關鍵字移動次數(shù)會隨之增加，例如：BubbleSort、QuickSort、HeapSort；仔細分析后得知，無論待排序是否排好，它每次運行都會有關鍵字的移動；每次運行程序，六種排序方式的關鍵字比較次數(shù)也會隨這操作次數(shù)的增加而增加。Mergesort排序空間性能比較差。六、用戶使用說明輸入：1-7數(shù)字，每次只能輸一次，從1到7都可以。七、參考文獻【1】王昆侖李紅.數(shù)據(jù)結(jié)構(gòu)與算法.中國鐵道出版社.2007年6月第一版八、附錄/*內(nèi)部排序算法比較【問題描述】在教科書中，各種內(nèi)部排序算法的時間復雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機數(shù)據(jù)比較各種算法的關鍵字比較次數(shù)和關鍵字移動次數(shù)，以取得直觀感受。 【任務要求】 對以下7種常用的內(nèi)部排序算法進行比較：冒泡排序、直接插入排序、簡單選擇排序、希爾排序、堆排序、歸并排序、快速排序。 待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機數(shù)程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較； 比較的指標為有關鍵字參加的比較次數(shù)和關鍵字的移動次數(shù)（關鍵字交換計為3次移動）。 最后要對結(jié)果作出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小的解釋。 【測試數(shù)據(jù)】由隨機數(shù)產(chǎn)生器生成*/#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>#include<time.h>#defineKeyTypeint#defineMAXSIZE100//***結(jié)構(gòu)體***typedefstruct{KeyTypekey;}RedType;typedefstruct{ RedTyper[MAXSIZE+1]; intlength; intinfo;//記錄關鍵字移動次數(shù) intcmp;//關鍵字的比較次數(shù)}SqList;voidchange(int*a,int*b);voidshow_paixu(SqList*L);intmenu_select();voidmain_menu();voidBubbleSort(SqList*L);voidInsertSort(SqList*L);voidSelectSort(SqList*L);voidShellinsert(SqList*L,intn);SqList*ShellSort(SqList*L);voidHeapSort(SqList*L);SqList*mergesort(SqList*L);voidmerge(SqList*L,intdelta);voidQuickSort(SqList*L,intlow,inthigh);//***兩個數(shù)交換***voidchange(int*a,int*b){ intc; c=*a; *a=*b; *b=c;}//***顯示函數(shù)***voidshow_paixu(SqList*L){ inti,j=-1;printf("該排序排序的結(jié)果：\n"); for(i=0;i<MAXSIZE;i++) { j++; if(j==10) { j=0; printf("\n"); } printf("%d",L->r[i].key); } printf("\n記錄關鍵字移動次數(shù)為:%d\n",L->info);printf("關鍵字的比較次數(shù)為：%d\n",L->cmp);}/**********************菜單************************/intmenu_select(){ intchioce; printf("***********************************************************\n"); printf("******************************菜單*************************\n"); printf("1.BubbleSort\n");//冒泡排序 printf("2.insertSort\n");//直接插入排序 printf("3.SelectSort\n");//簡單選擇排序 printf("4.ShellSort\n");//希爾排序 printf("5.HeapSort\n");//堆排序 printf("6.mergesort\n");//歸并排序 printf("7.QSort\n");//快速查找排序 printf("8.退出程序\n"); printf("***********************************************************\n"); printf("請輸入數(shù)字：1-7選擇相應的排序方式或操作：\n"); scanf("%d",&chioce); returnchioce;}/**********************主菜單************************/voidmain_menu(){SqListL,L1,L2,L3,L4,L5,L6; intj=-1,i=0;L.length=0; L.info=0; L.cmp=0; srand((unsigned)time(NULL)); printf("以下數(shù)據(jù)為需要排序的數(shù)據(jù)：\n");for(i=0;i<MAXSIZE;i++) { j++; L.r[i].key=rand()%200; L.length++; if(j==10) { j=0; printf("\n"); } printf("%d",L.r[i].key); } L1=L2=L3=L4=L5=L6=L; printf("\n"); for(i=0;i<7;i++) { switch(menu_select()) { case1:BubbleSort(&L); show_paixu(&L); break; case2:InsertSort(&L1); show_paixu(&L); break; case3:SelectSort(&L2); show_paixu(&L2); break; case4:show_paixu(ShellSort(&L3)); break; case5:HeapSort(&L4); show_paixu(&L4); break; case6:show_paixu(mergesort(&L5)); break; case7:QuickSort(&L6,0,L.length-1); show_paixu(&L6); break; } }}/******************************************************主程序*****************************************************************/intmain(){ main_menu();return0;}/******************************************************排序******************************************************************///***冒泡排序***voidBubbleSort(SqList*L){ inti=0,j=0,k=0,change; intn=L->length,x; // printf("%d",L->length); change=1;for(i=0;i<n-1&&change;++i) { change=0; for(j=0;j<n-i-1;++j) {if(L->r[j].key>L->r[j+1].key) { x=L->r[j].key; L->r[j].key=L->r[j+1].key; L->r[j+1].key=x; L->info+=3; change=1; } L->cmp++; } }}//***直接插入排序***voidInsertSort(SqList*L){ inti,j; RedTypek; for(i=1;i<L->length;i++) { k=L->r[i]; j=i-1; while(k.key<L->r[j].key) { L->r[j+1]=L->r[j]; L->info++; L->cmp++; j=j-1; } L->r[j+1]=k; L->info++; }}//***簡單選擇排序***voidSelectSort(SqList*L){intn,i,k,j; n=L->length-1; for(i=0;i<n;i++) { for(j=i+1;j<n+1;j++) { if(L->r[j].key<L->r[i].key) { change(&L->r[j].key,&L->r[i].key);L->info+=3; }L->cmp++; } }}//***希爾排序***voidShellinsert(SqList*L,intdelta){ inti,j,k,count=0; RedTypeflag; for(i=0;i<delta;i++) { for(j=i+delta;j<=L->length-1;j=j+delta) { flag.key=L->r[j].key; L->info++; k=j-delta; while((flag.key<L->r[k].key)&&k>=0) { L->r[k+delta].key=L->r[k].key; k=k-delta; L->cmp++;count=1; L->info++; } if(count==0) { L->cmp++; } L->r[k+delta].key=flag.key; L->info++; count=0; } }}SqList*ShellSort(SqList*L){ inti,di[100]; di[0]=L->length/2; for(i=0;i<L->length-1;i++) { Shellinsert(L,di[i]); di[i+1]=di[i]/2; if(di[i]==1) { break; } } returnL;}//***堆排序***voidSift(SqList*L,inti,intm){ intk,t; t=L->r[i].key;L->info++;k=2*i+1; while(k<m) { if((k<m-1)&&(L->r[k].key<L->r[k+1].key)) { k++; } if(t<L->r[k].key) { L->r[i].key=L->r[k].key; L->info++; i=k; k=2*i+1; } else { break; } L->cmp++; } L->r[i].key=t;L->info++;}voidHeapSort(SqList*L){ intn,i; RedTypetemp; n=L->length; for(i=n/2-1;i>=0;--i) { Sift(L,i,n); } for(i=n-1;i>=1;i--) { change(&L->r[0].key,&L->r[i].key); Sift(L,0,i); }}//***歸并排序***SqList*mergesort(SqList*L){ inti,di[100],flag=0,n; di[0]=2; n=L->length; for(i=0;i<L->length-1;i++) { merge(L,di[i]); di[i+1]=di[i]*2; if((di[i+1]>L->length)&&(di[i]<=L->len