各種排序?qū)嶒?yàn)報(bào)告

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

2、結(jié)點(diǎn)的元素。算法的平均時(shí)間復(fù)雜度為0(N log N)。程序?qū)崿F(xià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排序之后的數(shù)組為：vvendl;output();歸并排序算法思想：先將相鄰的個(gè)數(shù)為1的每兩組數(shù)據(jù)進(jìn)行排序合并；然后對上次歸并所得到的大小為2的組進(jìn)行相鄰歸并；如此反復(fù)，直到最

3、后并成一組，即排好序的一組數(shù)據(jù)。程序?qū)崿F(xiàn)及核心代碼的注釋：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)/此處為排序順序的關(guān)鍵，用小于表示從小到大排序is2k+=sui+;elseis2k+=suj+;while(iv=mid) is2k+=sui+;while(jv=high)is2k+=suj+;for(i=low; iv=high; i+) / 寫回原數(shù)組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);希爾排序算法思想：先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄 基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序。其中，子序列的構(gòu)成 不是簡單的 逐段分割”而是將分隔某個(gè) 增量”的記錄組成一個(gè)子序列。程序?qū)崿F(xiàn)及核心代碼的注釋:while(m) m/=2;if(m!=0)for(i=m; i=0&( tempsuj); j-=m) suj+m=suj;suj+m=temp;冒泡排序算法思想：1、先將一組未排序的數(shù)組的最后一個(gè)數(shù)與倒數(shù)第二個(gè)數(shù)進(jìn)行比較，并將較小 的數(shù)放于兩個(gè)

5、數(shù)中較前的位置，然后將比較后的較小的數(shù)與倒數(shù)第三個(gè)進(jìn)行比較，依次比 較到第一個(gè)數(shù)，即可得到第一個(gè)數(shù)是所有數(shù)中最小的數(shù)；2、然后再將數(shù)組的最后一個(gè)數(shù)3、倒數(shù)第二個(gè)數(shù)進(jìn)行比較，并將較小的數(shù)放于兩個(gè)數(shù)中較前的位置，依次比較到第二個(gè)數(shù),如此循環(huán)到只剩最后兩個(gè)比較，即得到排好序的一組數(shù)。程序?qū)崿F(xiàn)及核心代碼的注釋：for(i=0; isuj+1) temp=suj; suj=suj+1; suj+1=temp; flag=false;if(flag=true) break;vvendl;coutvv排序之后的數(shù)組為：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;快速排序任取待排序記錄序列中的某個(gè)記錄作為基準(zhǔn)，按照該記錄的關(guān)鍵字大小，將整個(gè)記錄 序列劃分為左右兩個(gè)子序列。左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于基準(zhǔn)記錄的關(guān)鍵字。右側(cè)子序列中所有記錄的關(guān)鍵字都大于基準(zhǔn)記錄的關(guān)鍵字。取序列第一個(gè)記錄為樞軸記錄，其關(guān)鍵字為Pivotkey;指針low指向序列第一個(gè)記錄位置(low=1)，指

8、針high指向序列最后一個(gè)記錄位置( High=SeqList.Len)(2)從high指向的記錄開始，向前找到第一個(gè)關(guān)鍵字的值小于Pivotkey的記錄，將其放到low指向的位置，low+ 從low指向的記錄開始，向后找到第一個(gè)關(guān)鍵字的值大于Pivotkey的記錄，將其放到high指向的位置，high重復(fù)2、3,直到low=high，將樞軸記錄放在 low( high)指向的位置。程序?qū)崿F(xiàn)及核心代碼的注釋：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 次順序后的結(jié)果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);基數(shù)排序(i)算法的基本思想 ：基數(shù)排序是屬于“分配式排序”，又稱“桶子法”，它是透過鍵值的部份資訊，將要排 序的元素分配至某些“桶”中，藉以達(dá)到排序的作用。最高位優(yōu)先法，簡稱 MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼 k1相等，再 對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān) 鍵碼kd對各子組排序后。再將各組連接起來，便得到一個(gè)有序序列。（2）程序?qū)崿F(xiàn)及核心代碼的注釋：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第一躺排序之后的數(shù)組為：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第二躺排序之后的數(shù)組為：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;折半排序算法思想：由于折半插入排序的基本操作是在一個(gè)有序表中進(jìn)行查找和插入，這個(gè)查找操作可利用折半查找來實(shí)現(xiàn)，由此進(jìn)行的插入排序稱之為折半插入排序。折半插入排序所 需附加存儲空間和直接插入排序相同，從時(shí)間上比較，這般插入排序僅減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動次數(shù)不變。因此，這般插入排序的時(shí)間復(fù)雜度仍為O (n2

13、)。程序?qū)崿F(xiàn)及核心代碼的注釋：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;直接插入排序算法思想：直接插入排序是一種最簡單的排序方法，它的基本操作是將一個(gè)記錄插入到一個(gè)已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增一的有序表。在自i-1起往前搜索的過程中，可以同時(shí)后移記錄。 整個(gè)排序過程為進(jìn)行 n-1趟插入，即:先將序列中的第一個(gè) 記錄看成是一個(gè)有序的子序列，然后從第二個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按

14、關(guān)鍵字非遞減有序序列為止。程序?qū)崿F(xiàn)及核心代碼的注釋：for(i=1; iN; i+)head=sui;for(j=0; ji; j+)if(headj; k-)suk=suk-1;suj=head;break;【三】詳細(xì)設(shè)計(jì)程序代碼：#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;將要排序的數(shù)組int ss10000= 372,209,53,942,547,234,645,468,7,83;將要排序的數(shù)組 int su10000; /將要排序的數(shù)組 int N=10;/數(shù)組的長度void input()/數(shù)組的輸入函數(shù)coutvv請輸入要排序的數(shù)組的長度 N ：;cinN;coutvv請輸入需要排序的數(shù)組：vvendl;for(int i=0; ivN; i+) cinssi;void output() /數(shù)組的輸出函數(shù)for(int i=0; ivN; i+) coutvvsuivv;coutvvendl;void head(int i,int m)/ 堆排序的

16、一個(gè)函數(shù)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排序之前的數(shù)組為：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排序之后的數(shù)組為：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) /此處為排序順序的關(guān)鍵，用小于表示從小到大排 序is2k+=sui+;elseis2k+=suj+;while(iv=mid) is2k+=sui+;while(jv=high) is2k+=suj+;for(i=low; iv=high; i+) / 寫回原數(shù)組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排序之前的數(shù)組為：vvendl; output();g(0,N-1);coutvv排序之后的數(shù)組為：vvendl; output();void xepx()/希爾排序int i,j,temp;int m=N;coutvv排序之前的數(shù)組為：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排序之后的數(shù)組為：vvendl;output();void

19、 mppx() 冒泡排序 int i,j,k;int temp,min;bool flag;coutvv排序之前的數(shù)組為：vvendl; output();for(i=0; isuj+1) temp=suj; suj=suj+1; suj+1=temp; flag=false; if(flag=true) break;coutvv排序之后的數(shù)組為：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+次順序后的結(jié)果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排序之前的數(shù)組為：vvendl; output();qsort(0,N-1);cout排序之后的數(shù)組為：vvendl; output();void jspx()/基數(shù)排序int i,j,k;int max=0;int a10100;int b10= 0;coutvv排序之前的數(shù)組為：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第一躺排序之后的數(shù)組為：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第二躺排序之后的數(shù)組為：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第三次排序之后的數(shù)組為：vvendl; output();void zbcrpx() /折半插入排序int i,j,k,m;int low,high,temp;coutvv排序之前的數(shù)組為：vvendl; output();for(i=1; ihigh+1; j-) suj=suj-1;suhigh+1=temp;coutvv排序之后的數(shù)組為：vvendl; output();void zjcrpx() /直接插入排序int i,j,k;int temp,head;coutvv排序之前的數(shù)組為：vvendl; output();for(i=1; ivN; i+)head=sui;for(j=0; jvi; j+)if(headvsuj) for(k=i; kj; k