1、【一】需求分析課程題目是排序算法的實現，課程設計一共要設計八種排序算法。這八種算法共包括：堆排序，歸并排序，希爾排序，冒泡排序，快速排序，基數排序，折半插入排序，直接插入排序。為了運行時的方便，將八種排序方法進行編號，其中1為堆排序，2為歸并排序，3為希爾排序，4為冒泡排序，5為快速排序，6為基數排序，7為折半插入排序8為直接插入 排序。【二】概要設計1.堆排序算法思想：堆排序只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。將序列所存儲的元素AN看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的元素均不大于(或不小于)其左右孩子(若存在)

2、結點的元素。算法的平均時間復雜度為0(N log N)。程序實現及核心代碼的注釋：for(j=2*i+1; j=m; j=j*2+1)if(j=suj)break;sui=suj;i=j;sui=temp;void dpx()/ 堆排序int i,temp;cout=0; i-)head(i,N);for(i=N-1; i0; i-)temp=sui;sui=su0;su0=temp;head(0,i-1);coutvv排序之后的數組為：vvendl;output();歸并排序算法思想：先將相鄰的個數為1的每兩組數據進行排序合并；然后對上次歸并所得到的大小為2的組進行相鄰歸并；如此反復，直到最

3、后并成一組，即排好序的一組數據。程序實現及核心代碼的注釋：int is21000;void bin(int low,int mid,int high)int i=low,j=mid+1,k=low;while(i=mid&jv=hig h)if(suiv=suj)/此處為排序順序的關鍵，用小于表示從小到大排序is2k+=sui+;elseis2k+=suj+;while(iv=mid) is2k+=sui+;while(jv=high)is2k+=suj+;for(i=low; iv=high; i+) / 寫回原數組sui=is2i;void g(int a,int b)if(avb)int

4、 mid=(a+b)/2;g(a,mid);g(mid+1,b); bin(a,mid,b);希爾排序算法思想：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄 基本有序”時，再對全體記錄進行一次直接插入排序。其中，子序列的構成 不是簡單的 逐段分割”而是將分隔某個 增量”的記錄組成一個子序列。程序實現及核心代碼的注釋:while(m) m/=2;if(m!=0)for(i=m; i=0&( tempsuj); j-=m) suj+m=suj;suj+m=temp;冒泡排序算法思想：1、先將一組未排序的數組的最后一個數與倒數第二個數進行比較，并將較小 的數放于兩個

5、數中較前的位置，然后將比較后的較小的數與倒數第三個進行比較，依次比 較到第一個數，即可得到第一個數是所有數中最小的數；2、然后再將數組的最后一個數3、倒數第二個數進行比較，并將較小的數放于兩個數中較前的位置，依次比較到第二個數,如此循環到只剩最后兩個比較，即得到排好序的一組數。程序實現及核心代碼的注釋：for(i=0; isuj+1) temp=suj; suj=suj+1; suj+1=temp; flag=false;if(flag=true) break;vvendl;coutvv排序之后的數組為：output();int K;int find(int i,int j)int temp;

6、bool flag=true; temp=sui;while(ivj)if(flag)while(tempv=suj) j-;if(i=j)break;if(i=j)break; sui=suj; while(temp=sui) i+;if(i=j)break;if(i=j)break; suj=sui;flag=false;elsewhile(temp=sui)i+； if(i=j) break;suj=sui;if(i=j)break;while(tempv=suj) j-;if(i=j) break;sui=suj; flag=true;for(i=1; iN; i+)head=sui;

7、 for(j=0; ji; j+)if(headj; k-) suk=suk-1;suj=head;break;for(i=1; ivN; i+)head=sui;for(j=0; jvi; j+)if(headj; k-)suk=suk-1;suj=head;break;快速排序任取待排序記錄序列中的某個記錄作為基準，按照該記錄的關鍵字大小，將整個記錄 序列劃分為左右兩個子序列。左側子序列中所有記錄的關鍵字都小于或等于基準記錄的關鍵字。右側子序列中所有記錄的關鍵字都大于基準記錄的關鍵字。取序列第一個記錄為樞軸記錄，其關鍵字為Pivotkey;指針low指向序列第一個記錄位置(low=1)，指

8、針high指向序列最后一個記錄位置( High=SeqList.Len)(2)從high指向的記錄開始，向前找到第一個關鍵字的值小于Pivotkey的記錄，將其放到low指向的位置，low+ 從low指向的記錄開始，向后找到第一個關鍵字的值大于Pivotkey的記錄，將其放到high指向的位置，high重復2、3,直到low=high，將樞軸記錄放在 low( high)指向的位置。程序實現及核心代碼的注釋：int find(int i,int j)int temp;bool flag=true; temp=sui; while(ivj)if(flag)while(tempv=suj) j-；

9、 if(i=j) break;if(i=j)break; sui=suj; while(temp=sui) i+;if(i=j)break;if(i=j)break; suj=sui; flag=false;elsewhile(temp=sui) i+;if(i=j)break;suj=sui;if(i=j)break;while(tempv=suj)j-；if(i=j)break;sui=suj;flag=true;sui=temp;coutvv1排完vvK+vv 次順序后的結果vvendl;output();return i;void qsort(int low,int high)if(l

10、owvhigh)int mid=find(low,high);qsort(low,mid-1);qsort(mid+1,high);基數排序(i)算法的基本思想 ：基數排序是屬于“分配式排序”，又稱“桶子法”，它是透過鍵值的部份資訊，將要排 序的元素分配至某些“桶”中，藉以達到排序的作用。最高位優先法，簡稱 MSD法：先按k1排序分組，同一組中記錄，關鍵碼 k1相等，再 對各組按k2排序分成子組，之后，對后面的關鍵碼繼續這樣的排序分組，直到按最次位關 鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。（2）程序實現及核心代碼的注釋：for(i=0; ivN; i+)if(maxsu

11、i) max=sui;aH(sui)bH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0)for(j=0; jbi; j+)suk+=aij;coutvv第一躺排序之后的數組為：vvendl; output();/第二次if(max/10=0)return ;for(i=0; i10; i+)bi=0;for(i=0; iN; i+)aHH(sui)bHH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0)for(j=0; jvbi; j+)suk+=aij;coutvv第二躺排序之后的數組為：vvendl;output();/第三

12、次if(max/100=0)return ;for(i=0; i10; i+)bi=0;for(i=0; iN; i+) aHHH(sui)bHHH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0)for(j=0; jbi; j+)suk+=aij;折半排序算法思想：由于折半插入排序的基本操作是在一個有序表中進行查找和插入，這個查找操作可利用折半查找來實現，由此進行的插入排序稱之為折半插入排序。折半插入排序所 需附加存儲空間和直接插入排序相同，從時間上比較，這般插入排序僅減少了關鍵字間的比較次數，而記錄的移動次數不變。因此，這般插入排序的時間復雜度仍為O (n2

13、)。程序實現及核心代碼的注釋：for(i=1; ivN; i+)temp=sui;low=0;high=i-1;while(lowv=high)m=(low+hig h)/2;if(temphigh+1; j-)suj=suj-1; suhigh+1=temp;直接插入排序算法思想：直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到一個已排好序的有序表中，從而得到一個新的、記錄數增一的有序表。在自i-1起往前搜索的過程中，可以同時后移記錄。 整個排序過程為進行 n-1趟插入，即:先將序列中的第一個 記錄看成是一個有序的子序列，然后從第二個記錄起逐個進行插入，直至整個序列變成按

14、關鍵字非遞減有序序列為止。程序實現及核心代碼的注釋：for(i=1; iN; i+)head=sui;for(j=0; ji; j+)if(headj; k-)suk=suk-1;suj=head;break;【三】詳細設計程序代碼：#include viostream#include #include #include valgorithm#include #define H(X) (X%10)#define HH(X) (X%100/10)#define HHH(X) (X/100)using namespace std;int ss10000= 32,37,64,87,16,12,24,

15、32;將要排序的數組int ss10000= 372,209,53,942,547,234,645,468,7,83;將要排序的數組 int su10000; /將要排序的數組 int N=10;/數組的長度void input()/數組的輸入函數coutvv請輸入要排序的數組的長度 N ：;cinN;coutvv請輸入需要排序的數組：vvendl;for(int i=0; ivN; i+) cinssi;void output() /數組的輸出函數for(int i=0; ivN; i+) coutvvsuivv;coutvvendl;void head(int i,int m)/ 堆排序的

16、一個函數int j;int temp;temp=sui;for(j=2*i+1; jv=m; j=j*2+1)if(j=suj)break;sui=suj;i=j；sui=temp;void dpx()/ 堆排序int i,temp;coutvv排序之前的數組為：vvendl;output();for(i=N/2-1; i=0; i-)head(i,N);for(i=N-1; i0; i-)temp=sui;sui=su0;su0=temp; head(0,i-1);coutvv排序之后的數組為：vvendl;output();int is21000;void bing(int low,int

17、 mid,int high)int i=low,j=mid+1,k=low;while(iv=mid&jv=high) if(suiv=suj) /此處為排序順序的關鍵，用小于表示從小到大排 序is2k+=sui+;elseis2k+=suj+;while(iv=mid) is2k+=sui+;while(jv=high) is2k+=suj+;for(i=low; iv=high; i+) / 寫回原數組sui=is2i;void g(int a,int b)if(avb)int mid=(a+b)/2;g(a,mid);g(mid+1,b); bing(a,mid,b);void gbpx

18、()/歸 并排序coutvv排序之前的數組為：vvendl; output();g(0,N-1);coutvv排序之后的數組為：vvendl; output();void xepx()/希爾排序int i,j,temp;int m=N;coutvv排序之前的數組為：vvendl;output();while(m)m/=2;if(m!=0)for(i=m; ivN; i+) if(suiv sui-m)temp=sui;for(j=i-m; j=0&(tempvsuj); j-=m) suj+m=suj;suj+m=temp;coutvv排序之后的數組為：vvendl;output();void

19、 mppx() 冒泡排序 int i,j,k;int temp,min;bool flag;coutvv排序之前的數組為：vvendl; output();for(i=0; isuj+1) temp=suj; suj=suj+1; suj+1=temp; flag=false; if(flag=true) break;coutvv排序之后的數組為：vvendl; output();int K;int find(int i,int j)int temp;bool flag=true;temp=sui;while(ivj)if(flag)while(tempv=suj)j-; if(i=j) br

20、eak;if(i=j)break;sui=suj; while(temp=sui) i+； if(i=j) break;if(i=j)break;suj=sui; flag=false;elsewhile(temp=sui) i+; if(i=j) break;suj=sui;if(i=j) break;while(temp=j)break;sui=suj; flag=true;sui=temp;coutvv排完K+次順序后的結果vvendl; output();return i;void qsort(int low,int high)if(lowvhigh)int mid=find(low,

21、high);qsort(low,mid-1);qsort(mid+1,high);void kspx() 快速排序K=0;coutvv排序之前的數組為：vvendl; output();qsort(0,N-1);cout排序之后的數組為：vvendl; output();void jspx()/基數排序int i,j,k;int max=0;int a10100;int b10= 0;coutvv排序之前的數組為：vvendl; output();for(i=0; ivN; i+)if(maxvsui) max=sui; aH(sui)bH(sui)+=sui;k=0;for(i=0; ivl

22、0; i+)if(bi!=0) for(j=0; jvbi; j+) suk+=aij;coutvv第一躺排序之后的數組為：vvendl; output();/第二次if(max/10=0) return ;for(i=0; ivl0; i+)bi=0;for(i=0; ivN; i+)aHH(sui)bHH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0) for(j=0; jbi; j+) suk+=aij;coutvv第二躺排序之后的數組為：vvendl; output();/第三次if(max/100=0)return ;for(i=0; i10; i+

23、)bi=0;for(i=0; iN; i+)aHHH(sui)bHHH(sui)+=sui;k=0;for(i=0; i10; i+)if(bi!=0) for(j=0; jbi; j+) suk+=aij;coutvv第三次排序之后的數組為：vvendl; output();void zbcrpx() /折半插入排序int i,j,k,m;int low,high,temp;coutvv排序之前的數組為：vvendl; output();for(i=1; ihigh+1; j-) suj=suj-1;suhigh+1=temp;coutvv排序之后的數組為：vvendl; output();void zjcrpx() /直接插入排序int i,j,k;int temp,head;coutvv排序之前的數組為：vvendl; output();for(i=1; ivN; i+)head=sui;for(j=0; jvi; j+)if(headvsuj) for(k=i; kj; k