內(nèi)排序?qū)嶒?yàn)報告

地環(huán)院09級地信班實(shí)驗(yàn)報告學(xué)號：2011年1月7日院系地環(huán)學(xué)院班級課程名稱數(shù)據(jù)結(jié)構(gòu)姓名同組者無實(shí)驗(yàn)名稱排序過程實(shí)驗(yàn)?zāi)康暮鸵螅赫莆諑追N有用的排序方法。希爾排序希爾排序通俗理解起來就一句話，每隔幾個數(shù)字取兩個數(shù)，并按你期望的大小把他們交換了。其原理就是使得一個無序的數(shù)組里，逐漸產(chǎn)生一小片一小片有序的序列，到最后，把這些有序的序列再拼接到一起，從而完成了整個無序到有序的排序過程。以下面的一組數(shù)據(jù)為例來加以驗(yàn)證012345678956277089732023564813下面的程序就是一個簡單測試希爾排序的程序。具體程序見1.c#include<stdio.h>voidssort(intA[],intn,intsp)//簡單的判斷每隔sp個數(shù)就進(jìn)行交換{ inti,j,t; for(i=0;i<n-sp;i++)//注意i的取值范圍n-sp for(j=i;j<n-sp;j++) if(A[j]>A[j+sp]) { t=A[j];A[j]=A[j+sp];A[j+sp]=t;//交換程序 }}main(){ inta[]={56,27,70,89,73,20,23,56,48,13},n=10,sp=5; inti,j,t; for(i=0;i<n-sp;i++) for(j=i;j<n-sp;j+=sp) if(a[j]>a[j+sp]) { t=a[j];a[j]=a[j+sp]; a[j+sp]=t; } for(j=0;j<n;j++) printf("%4d",a[j]); printf("\n");//下面三句代碼分別為隔5個、3個、1個進(jìn)行交換，不管怎么樣，最后必須為1 ssort(a,10,5); ssort(a,10,3); ssort(a,10,1); for(i=0;i<10;i++) printf("%4d",a[i]); printf("\n");}上面的程序代碼直接寫在了main()函數(shù)中，所以為了方便以后引用，我們做出修改完善的程序見2.c#include<stdio.h>voidssort(intA[],intn,intsp){ inti,j,t; for(i=0;i<n-sp;i++) for(j=i;j<n-sp;j++) if(A[j]>A[j+sp]) { t=A[j];A[j]=A[j+sp];A[j+sp]=t; }}voidshellsort(intA[],intn,intD[],intNumD)//希爾排序的程序，注意該函數(shù)中的幾個參數(shù){ inti; for(i=0;i<NumD;i++) ssort(A,n,D[i]);}main(){ inta[]={56,27,70,89,73,20,23,56,48,13},i,D[]={5,3,1}; shellsort(a,10,D,3);//引用希爾排序 for(i=0;i<10;i++) printf("%4d",a[i]); printf("\n");}到此為止，希爾排序完成。歸并排序#include<stdio.h>#include<stdlib.h>voidmerge(intA[],intC[],intL,intM,intR)//數(shù)組A裝的是需要排序的數(shù)據(jù)，數(shù)組C是輔助存儲空間，L是數(shù)組A的左下標(biāo)，R是數(shù)組A的右下標(biāo)，M是介于L和R之間的數(shù)。{ inti,j,k;//申請三個整型變量。 for(i=L;i<=M;i++)//將數(shù)組A中從第一個數(shù)到第M個數(shù)裝入到數(shù)組C中，此時數(shù)組C中有M個數(shù)據(jù)。 C[i]=A[i]; j=R;//給j賦初值。 for(i=M+1;i<=R;i++)//在數(shù)組A中的第m+1個數(shù)到最后一個數(shù)依次賦給C數(shù)組中的第M個數(shù)以后。 C[i]=A[j--]; i=L;j=R;//重新給i,j賦值。 for(k=L;k<=R;k++)//k的取值范圍為C數(shù)組中的最小的下標(biāo)到最大下標(biāo)志。 A[k]=(C[i]<C[j])?C[i++]:C[j--];//把數(shù)組C中的數(shù)據(jù)從第一個和最后一個比較。}1234567891023114566733221589456數(shù)組ALvoidMSort(intA[],intC[],intL,intR)//將數(shù)組C劃分為若干部分進(jìn)行排序。{ intM;//申請一個整型變量。 M=(L+R)/2;//M為數(shù)組A的中間下標(biāo)值。 if(R<=L)return;//如果右下標(biāo)小于左下標(biāo)，則直接退出。 MSort(A,C,L,M);//用遞歸對數(shù)組A的左半部分排序。 MSort(A,C,M+1,R);//用遞歸對數(shù)組A的右半部分排序。 merge(A,C,L,M,R);//以數(shù)組的中間下標(biāo)分成兩部分分別排序。}voidmergesort(intA[],intn)//對數(shù)組A進(jìn)行排序。{ int*C;//構(gòu)造輔助存儲數(shù)組C。 C=(int*)malloc(sizeof(int)*n);//為數(shù)組A申請存儲空間。 MSort(A,C,0,n-1);//調(diào)用排序函數(shù)。 free(C);//釋放存儲空間C。}main(){ intA[]={0}; scanf("%d",&A[i]);mergesort(A,n); for(i=0;i<n;i++) printf("%d\t",A[i]); printf("\n");}快速排序以下快速排序的圖解說明排序的原理：快速排序示意圖#include<stdio.h>voidQsort(intA[],intlow,inthigh)//快速排序，low是數(shù)組A的最小下標(biāo)，high是最大下標(biāo)值{ inti,j,p;//i,j控制循環(huán)，p存儲支點(diǎn) i=low;j=high; if(i>=j)return;//遞歸返回的條件 p=A[i];//將A[i]給p作為支點(diǎn) while(i<j)//一趟排序 { while(i<j&&A[j]>=p)//當(dāng)從右往左走時，A[j]大于支點(diǎn)值時，一直往左走，否則，退出循環(huán) j--; if(i<j)//當(dāng)A[j]小于支點(diǎn)值時 { A[i]=A[j];//將A[j]給A[i],也就是移到左側(cè) i++;//i加1，即i右移 } while(i<j&&A[i]<p)//當(dāng)從左往右走時，A[i]小于于支點(diǎn)值時，一直往右走，否則，退出循環(huán) i++; if(i<j)//當(dāng)A[i]大于支點(diǎn)值時 { A[j]=A[i];//將A[i]給A[j],也就是移到右側(cè) j--;//j減1，即j向左移 } } A[i]=p;//將支點(diǎn)給A[i] Qsort(A,low,i-1);//支點(diǎn)左側(cè)再做快速排序 Qsort(A,i+1,high);//支點(diǎn)右側(cè)再做快速排序}main(){ intA[6]={30,10,4,9,5,20}; inti; Qsort(A,0,5); printf("排序結(jié)果是：\n"); for(i=0;i<6;i++) printf("%4d",A[i]); printf("\n");}基數(shù)排序#include<stdio.h>#include<stdlib.h>voidJishuSort(intA[],intn)//基數(shù)排序{ int*C;//說明一指針C,用來構(gòu)造動態(tài)數(shù)組 inti,m,max=A[0],t=0; for(i=0;i<n;i++) if(max<A[i])//求數(shù)組A中的最大值，用來申請C數(shù)組所占的存儲空間 max=A[i]; max++;//最大值++ C=(int*)malloc(sizeof(int)*max);//給數(shù)組C申請存儲空間 for(i=0;i<max;i++) C[i]=0;//初始化數(shù)組C for(i=0;i<n;i++) { m=A[i];//將數(shù)組A的值給m C[m]=1;//將數(shù)組C中以數(shù)組A中的值為下標(biāo)的值賦予1 } for(m=0;m<max;m++) if(C[m]!=0)//判斷C數(shù)組中值是否為0 A[t++]=m;//如不為0，則裝入A中，并且A中數(shù)組的下標(biāo)是從0開始的}main(){ intA[]={22,3,45,67,21,23}; inti; JishuSort(A,6); printf("排序結(jié)果是：\n"); for(i=0;i<6;i++) printf("%4d",A[i]);//打印排序后的數(shù)組 printf("\n");}堆排序堆排序的原理是按給出的數(shù)據(jù)構(gòu)造成二叉樹，再找出第一個最大數(shù)，把這個最大數(shù)去掉后，再在其他的數(shù)據(jù)中找出最大數(shù)，依次照完所有的數(shù)。#include<stdio.h>voidHeadAdjust(inta[],ints,intn)//調(diào)整二叉樹使其變?yōu)榇箜敹?。{ inti,t;//申請兩個整型變量。 while(2*s+1<n)//如果二叉樹中第S個結(jié)點(diǎn)的左孩子標(biāo)號小于n。 { i=2*s+1;//將標(biāo)號附為i。 if((i+1)<n)//如果二叉樹中第S個結(jié)點(diǎn)的右孩子標(biāo)號小于n。 { if(a[i]<a[i+1])i++;//將二叉樹的左右孩子結(jié)點(diǎn)值調(diào)換。 } if(a[s]<a[i])//如果二叉樹中第S個結(jié)點(diǎn)的結(jié)點(diǎn)值小于右孩子結(jié)點(diǎn)值，將他們兩結(jié)點(diǎn)值調(diào)換。。 { t=a[s]; a[s]=a[i]; a[i]=t; s=i; } else break; }}voidHeadSort(intA[],intn)//構(gòu)造函數(shù)檢查每一個結(jié)點(diǎn)。voidHeadSort(intA[],intn)//構(gòu)造函數(shù)檢查每一個結(jié)點(diǎn)。{ inti,t; for(i=n/2-1;i>=0;i--) HeadAdjust(A,i,n);//調(diào)用上面的函數(shù)測試其中的結(jié)點(diǎn)。 for(i=n-1;i>=0;i--)//對剩下的其他節(jié)點(diǎn)再進(jìn)行調(diào)整。 { t=A[0]; A[0]=A[i]; A[i]=t; HeadAdjust(A,0,i); }}這里二叉樹如下，它的過程是通過調(diào)整二叉樹先找出這些數(shù)中的第一個最大值在從剩下的數(shù)中找出最大值，依次直到這些數(shù)據(jù)找完。第一步調(diào)整。main(){ inti,A[]={12,34,45,56,3,2,45,66,67,43}; HeadSort(A,10); for(i=0;i<10;i++) printf("%d",A[i]); printf("\n"); /*inti,A[]={0},n; printf("請輸入要排序的數(shù)據(jù)個數(shù)n\n"); scanf("%d",&n); printf("請輸入要排序的數(shù)據(jù)\n")