數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序算法演示系統(tǒng)

1、1. 設(shè)計(jì)目的隨著計(jì)算機(jī)技術(shù)的發(fā)展，各種排序算法不斷的被提出。排序算法在計(jì)算機(jī)科學(xué)中有非常重要的意義，且應(yīng)用很廣泛。在以后的發(fā)展中排序?qū)ξ覀兊膶W(xué)習(xí)和生活的影響會(huì)逐漸增大，很有必要學(xué)習(xí)排序知識(shí)。此次課程設(shè)計(jì)一方面使自己掌握排序的知識(shí)，另一方面鍛煉一下團(tuán)隊(duì)合作開(kāi)發(fā)系統(tǒng)的能力。2.1 設(shè)計(jì)內(nèi)容和要求設(shè)計(jì)內(nèi)容：（1）實(shí)現(xiàn)各種內(nèi)部排序。包括直接插入排序，希爾排序，冒泡排序，快速排序，直接選擇排序，歸并排序，堆排序。（2）待排序的元素的關(guān)鍵字為整數(shù)或（字符）?？捎秒S機(jī)數(shù)據(jù)和用戶輸入數(shù)據(jù)作測(cè)試比較。比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)(關(guān)鍵字交換以3次計(jì))。（3）演示程序以人機(jī)對(duì)話的形式進(jìn)行

2、。每次測(cè)試完畢顯示各種比較指標(biāo)值的列表，以便比較各種排序的優(yōu)劣。3. 本設(shè)計(jì)所采用的數(shù)據(jù)結(jié)構(gòu)typedef struct int key;RecType;4. 功能模塊詳細(xì)設(shè)計(jì)4.1 詳細(xì)設(shè)計(jì)思想主函數(shù)：#include#include#include #define L 8 /排序元素個(gè)數(shù)#define FALSE 0#define TRUE 1typedef struct int key; RecType;RecType RL;int num; int sum;int sun; /定義排序趟數(shù)的全局變量 /主函數(shù)int main() Seqlist S; int i,k; char ch1

3、,ch2,q; printf(ntt 排序算法演示系統(tǒng)nntt請(qǐng)輸入%d個(gè)待排序的數(shù)據(jù)：,L);for(i=1;i=L;i+) scanf(%d,&Si.key); getchar(); printf(tt); ch1=y; while(ch1=y) printf(n); printf(ntt 菜 單 n); printf(ntt*n); printf(ntt 1-更新排序數(shù)據(jù) 2-直接插入排序 n); printf(ntt 3-希 爾 排 序 4-冒 泡 排 序 n); printf(ntt 5-快 速 排 序 6-直接選擇排序 n); printf(ntt 7-堆 排 序 8-歸 并 排

4、序 n); printf(ntt * 0-退 出 * n); printf(ntt*n); printf(ntt請(qǐng)選擇:); scanf(%c,&ch2); getchar(); for(i=1;i=L;i+) Ri.key=Si.key; switch(ch2) case 1: printf(ntt請(qǐng)輸入%d個(gè)待排序數(shù)據(jù)ntt,L); for(i=1;i=L;i+) scanf(%d,&Si.key); getchar(); printf(tt); printf(ntt數(shù)據(jù)輸入完畢！); break; case 2: Insertsort(); break; case 3: Shellsor

5、t(); break; case 4: Bubblesort(); break; case 5: printf(ntt原始數(shù)據(jù)為（按回車鍵開(kāi)始排序）：ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); num=0;sun=0;sum=0; Quicksort(1,L); printf(ntt排序最終結(jié)果是：ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); printf(ntt比較次數(shù)是：%dntt,sum);printf(ntt交換次數(shù)是：%dntt,sun); break; case

6、 6: Selectsort(); break; case 7: Heap(); break;case 8: Mergesort(); break; case 0: ch1=n; break; default: system(cls);/清屏 printf(ntt對(duì)不起，您輸入有誤，請(qǐng)重新輸入！n); break; if(ch2!=0) if(ch2=2|ch2=3|ch2=4|ch2=5|ch2=6|ch2=7|ch2=8) printf(nntt排序完畢！); printf(ntt按回車鍵繼續(xù)！); q=getchar(); if(q!=n) getchar(); ch1=n; retur

7、n 1;/系統(tǒng)主界面4.1.1 冒泡排序核心思想 依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面，第一輪比較后，最大的數(shù)便被放到了最后；第二輪操作前n-1個(gè)數(shù)據(jù)（假設(shè)有n個(gè)數(shù)據(jù)），依然是依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面，倒數(shù)第二個(gè)數(shù)便是第二大的數(shù)；同理第i輪操作前n-i+1的數(shù)據(jù)（假設(shè)i取值是從1開(kāi)始的），則n-i+i位置上的數(shù)據(jù)為第i大的數(shù)據(jù)。一共有n-1輪，第i輪比較中共比較n-i次比較。核心代碼void Bubblesort() int i,j,k,x=0,y=0,m=0; int exchange=TRUE;/標(biāo)志位exchange初始化為TRUE 1 print

8、f(ntt原始數(shù)據(jù)為（按回車鍵開(kāi)始排序）：ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); for(i=1;iL&exchange=TRUE;i+)/外層對(duì)總的循環(huán)次數(shù)執(zhí)行次數(shù) exchange=FALSE; for(j=1;j=L+1-i;j+) /內(nèi)層相鄰記錄的交換與比較 m+;/比較次數(shù)+ if(Rj.keyRj-1.key) R0.key=Rj.key; Rj.key=Rj-1.key; Rj-1.key=R0.key; exchange=TRUE;y+;/移動(dòng)次數(shù)+ m-;/比較次數(shù) if(exchange

9、) /輸出語(yǔ)句 printf(tt第%d趟冒泡排序的結(jié)果為：ntt,i); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); printf(ntt比較次數(shù)是：tt); printf(%d,m); printf(ntt移動(dòng)次數(shù)是：tt); printf(%d,y); printf(ntt排序最終結(jié)果是：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); 4.1.2 快速排序核心思想 首先檢查數(shù)據(jù)列表中的數(shù)據(jù)數(shù)，如果小于兩個(gè)，則直接退出程序。如果有超過(guò)兩個(gè)以上的數(shù)據(jù)，就選擇一個(gè)分割點(diǎn)將數(shù)據(jù)分成兩個(gè)部分

10、，小于分割點(diǎn)的數(shù)據(jù)放在一組，其余的放在另一組，然后分別對(duì)兩組數(shù)據(jù)排序。 通常分割點(diǎn)的數(shù)據(jù)是隨機(jī)選取的。這樣無(wú)論你的數(shù)據(jù)是否已被排列過(guò)，你所分割成的兩個(gè)字列表的大小是差不多的。而只要兩個(gè)子列表的大小差不多核心代碼void Quicksort(int low,int high)/該程序?yàn)檫f歸算法實(shí)現(xiàn) int i=low,j=high,k; R0.key=Rlow.key; while(ij) while(ij&R0.key=Rj.key) /右側(cè)掃描 j-; sum+; if(ij) Ri.key=Rj.key;/交換 i+;sun+; while(ij&Ri.keyR0.key)/左側(cè)掃描 i+

11、; sum+; if(ij) Rj.key=Ri.key;/交換 j-; sun+; Ri.key=R0.key; num+; /輸出語(yǔ)句包括排序的結(jié)果及次數(shù) printf(tt第%d趟快速排序的結(jié)果為：ntt,num); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); if(lowi-1) Quicksort(low,i-1);/遞歸部分(左側(cè)) if(j+1high) Quicksort(j+1,high);/遞歸部分(右側(cè))4.1.3 直接插入排序核心思想經(jīng)過(guò)i-1遍處理后,L1.i-1己排好序。第i遍處理僅將Li插入L

12、1.i-1的適當(dāng)位置，使得L1.i又是排好序的序列。要達(dá)到這個(gè)目的，我們可以用順序比較的方法。首先比較Li和Li-1，如果Li-1 Li，則L1.i已排好序，第i遍處理就結(jié)束了；否則交換Li與Li-1的位置，繼續(xù)比較Li-1和Li-2，直到找到某一個(gè)位置j(1ji-1)，使得Lj Lj+1時(shí)為止核心代碼void Insertsort() int i,j,k,m=0,x=0; /初始化比較次數(shù)變量m，移動(dòng)次數(shù)變量x printf(ntt原始數(shù)據(jù)為：ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); /主要運(yùn)行部分 for

13、(i=2;i=L;i+) if(Ri.keyRi-1.key) R0=Ri; j=i-1; while(R0.keyRj.key) Rj+1=Rj; j-; Rj+1=R0; x+; m+; /輸出語(yǔ)句包括排序的結(jié)果及次數(shù) printf(tt第%d趟直接插入排序的結(jié)果為：ntt,m); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); printf(n); printf(ntt比較次數(shù)是：tt); printf(%d,m); printf(ntt移動(dòng)次數(shù)是：tt); printf(%d,x); printf(ntt排序最終結(jié)果是

14、：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); 4.1.4 希爾排序核心思想 先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂：诵拇avoid Shellsort() int i,j,gap,x,k,y=0,m=0; /初始化比較次數(shù)變量m，移動(dòng)次數(shù)變量y printf(ntt原始數(shù)據(jù)為：ntt); for(k=1;k0) fo

15、r(i=gap+1;i0) if(Rj.keyRj+gap.key) x=Rj.key;/交換語(yǔ)句 Rj.key=Rj+gap.key; Rj+gap.key=x; j=j-gap; y+;/移動(dòng)次數(shù)+ else j=0; gap=gap/2; m+;/比較次數(shù)+ /輸出語(yǔ)句包括排序的結(jié)果及次數(shù) printf(tt第%d趟希爾排序的結(jié)果為：ntt,m); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); printf(ntt比較次數(shù)是：tt); printf(%d,m); printf(ntt移動(dòng)次數(shù)是：tt); printf(

16、%d,y); printf(ntt排序最終結(jié)果是：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); printf(n); 4.1.5 直接選擇排序核心思想 第一次從R0Rn-1中選取最小值，與R0交換，第二次從R1Rn-1中選取最小值，與R2交換，.， 第i次從Ri-1Rn-1中選取最小值，與Ri-1交換，.，第n-1次從Rn-2Rn-1中選取最小值，與Rn-2交換,總共通過(guò)n-1次,得到一個(gè)按排序碼從小到大排列的有序序列.核心代碼void Selectsort() int i,j,k,h,x=0,y=0; printf(ntt原始數(shù)據(jù)為（按回車鍵開(kāi)始排序）：

17、ntt); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); for(i=1;iL;i+) h=i; for(j=i+1;j=L;j+) x+; /比較次數(shù) if(Rj.keyRh.key) h=j; /確定最小值 if(h!=i) R0.key=Ri.key; Ri.key=Rh.key; Rh.key=R0.key; y+; /移動(dòng)次數(shù) printf(tt第%d趟選擇排序的結(jié)果為：ntt,i); for(k=1;k=L;k+) printf(%5d,Rk.key); getchar(); printf(n); /輸出語(yǔ)句包括

18、排序的結(jié)果及次數(shù) printf(ntt比較次數(shù)：%d,x); printf(ntt移動(dòng)次數(shù)：%d,y); printf(ntt排序最終結(jié)果是：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); printf(n); 4.1.6 堆排序核心思想 堆排序是一樹(shù)形選擇排序，在排序過(guò)程中，將R1.N看成是一顆完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。將原始記錄序列建成一個(gè)堆，成為初始堆，并輸出堆頂元素；調(diào)整剩余的記錄序列，使之成為一個(gè)新堆，再輸出堆頂元素；如此反復(fù)進(jìn)行，當(dāng)堆中只有一個(gè)元素時(shí)，整個(gè)序列的排序結(jié)束，輸出的序列

19、便是原始序列的非遞減有序序列。在堆排序的過(guò)程中，主要負(fù)責(zé)兩方面的工作：一是如何將原始記錄序列構(gòu)造成一個(gè)堆，即建立初始堆；二是輸出堆頂元素后，如何將剩余記錄整理成一個(gè)新堆。核心代碼/建堆void CreateHeap(int root,int index,int *x,int *y) int j,temp,finish; j=2*root; /j指向左孩子 temp=Rroot.key; finish=0; while(j=index&finish=0) if(jindex) if(Rj.key=Rj.key) finish=1; else Rj/2.key=Rj.key; (*y)+; j=j

20、*2; *x = *x+2; Rj/2.key=temp; (*y)+;/堆排序void Heapsort() int i,j,temp,k,x=0,y=0; for(i=(L/2);i=1;i-) /建立初始堆 CreateHeap(i,L,&x,&y); x=0; y=0; for(i=L-1,k=1;i=1;i-,k+) /將堆中根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換 temp=Ri+1.key; Ri+1.key=R1.key; R1.key=temp; CreateHeap(1,i,&x,&y); printf(tt第%d趟堆排序的結(jié)果為：ntt,k); for(j=1;j=L;j+) print

21、f(%5d,Rj.key); getchar(); printf(n); printf(ntt比較次數(shù)是：%dtt,x); printf(ntt移動(dòng)次數(shù)是：%dtt,y);void Heap() int i; printf(ntt原始數(shù)據(jù)為（按回車鍵開(kāi)始排序）：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); getchar(); printf(n); Heapsort(); printf(ntt排序最終結(jié)果是：ntt); for(i=1;i=L;i+) printf(%5d,Ri.key); printf(n);4.1.7 歸并排序核心思想將有n個(gè)記錄的原始

22、序列看作n個(gè)有序子序列，每個(gè)子序列的長(zhǎng)度為1，然后從第一個(gè)子序列開(kāi)始，把相鄰的子序列兩兩合并，得到n/2個(gè)長(zhǎng)度為2或1的子序列（當(dāng)子序列個(gè)數(shù)為奇數(shù)時(shí)，最后一組合并得到的序列長(zhǎng)度為1），把這一過(guò)程稱為一次歸并排序，對(duì)第一次歸并排序后的n/2個(gè)子序列采用上述方法繼續(xù)順序成對(duì)歸并，如此重復(fù)，當(dāng)最后得到的長(zhǎng)度為n的一個(gè)子序列時(shí)，該子序列便是原始序列歸并排序后的有序序列。核心代碼void Merge(int low,int mm,int high,int *x,int *y)/兩個(gè)有序序列的合并 int i=low,j=mm+1,p=0; RecType *R1; /i對(duì)第一個(gè)開(kāi)始到結(jié)尾，j從第二個(gè)開(kāi)始到結(jié)尾 R1=new RecTypehigh-low+1; if(!R1) printf(內(nèi)存不足！); while(i=mm&j=high)/兩序列從起始位置開(kāi)始將小的元素放入到R1中 R1p+=(Ri.key=Rj.key)?Ri+:Rj+; (*x)+; (*y)+; while(i=mm