歸并排序分治策略的設(shè)計與實現(xiàn)

1、實驗名稱歸并排序分治策略的設(shè)計與實現(xiàn)實驗方案實驗成績實驗日期實驗室信息系統(tǒng)設(shè)計與仿真室I實驗操作實驗臺號班級姓名實驗結(jié)果一、實驗?zāi)康?、熟悉分治法求解問題的抽象控制策略；2、熟悉在順序存儲表示下求解分類問題的遞歸算法設(shè)計；3、通過實例轉(zhuǎn)換,掌握分治法應(yīng)用。二、實驗任務(wù)從文件中讀取數(shù)據(jù)信息；利用歸并排序算法，進(jìn)行排序；輸出排序結(jié)果。三、實驗設(shè)計方案1、結(jié)構(gòu)體設(shè)計用數(shù)組存放排序數(shù)據(jù)。2、自定義函數(shù)設(shè)計函數(shù)原型聲明intinput(intA);/從文件讀入待排序的數(shù)據(jù)voidmerge(intA,intlow,intmid,inthigh);/兩個相鄰有序數(shù)組的歸并voidmergesort(int

2、A,intlow,inthigh);/歸并排序voidinput(intA,intn);/輸出排序結(jié)果兩個相鄰的有序子數(shù)組的合并思路:從兩個已排好序的子數(shù)組的首元素開始，依次比較大小，按從小到大的順序存放在b數(shù)組中，然后轉(zhuǎn)存到A數(shù)組中。voidmerge(intA,intlow,intmid,inthigh)intbN;inti,j,k=0;intl=low;/已排序部分1的起始下標(biāo)inth=mid+1;/已排序部分2的起始下標(biāo)while(l=mid&h=high)/兩個有序部分合并到b數(shù)組中if(AlAh)bk+=Al+;elsebk+=Ah+;while(l=mid)/剩余部分1bk+=A

3、l+;while(h=high)/剩余部分2bk+=Ah+;for(i=0,j=low;ivk;i+,j+)將排好序的數(shù)組中的數(shù)復(fù)制到原來的A數(shù)組中去Aj=bi;整個數(shù)組的分治歸并思路：利用遞歸思想，將整個數(shù)組分為兩個(可遞歸排序)的子數(shù)組，然后進(jìn)行歸并。voidmergesort(intA,intlow,inthigh)intmid;/切分點if(lowhigh)/當(dāng)low小于high的時候，可繼續(xù)分治mid=(low+high)/2;/遞歸思想mergesort(A,low,mid);/先分治mergesort(A,mid+1,high);merge(A,low,mid,high);/再歸并3、主函數(shù)設(shè)計思路：主函數(shù)實現(xiàn)實驗任務(wù)的基本流程。voidmain()intAN,n;/定義數(shù)組An=input(A);讀入文件數(shù)據(jù)到數(shù)組A,返回數(shù)據(jù)個數(shù)mergesort(A,0,n-1);/對數(shù)組A進(jìn)行歸并排序output(A,n);/輸出排序結(jié)果四、測試1、測試數(shù)據(jù)下面測試數(shù)據(jù)存放在in.txt文件中，第一行表示數(shù)據(jù)個數(shù)，第二行表示數(shù)據(jù)內(nèi)容。101011269741352、測試結(jié)果編碼結(jié)果存放