排序 - 歸並排序（一）

　　歸並排序(Merge Sort)是利用歸並技術來進行排序歸並是指將若干個已排序的子文件合並成一個有序的文件

　　兩路歸並算法

　　算法基本思路

　　設兩個有序的子文件(相當於輸入堆)放在同一向量中相鄰的位置上R[lowm]R[m+high]先將它們合並到一個局部的暫

　　存向量R(相當於輸出堆)中待合並完成後將R復制回R[lowhigh]中

　　()合並過程

　　合並過程中設置ij和p三個指針其初值分別指向這三個記錄區的起始位置合並時依次比較R[i]和R[j]的關鍵字取關鍵

　　字較小的記錄復制到R[p]中然後將被復制記錄的指針i或j加以及指向復制位置的指針p加

　　重復這一過程直至兩個輸入的子文件有一個已全部復制完畢(不妨稱其為空)此時將另一非空的子文件中剩余記錄依次復制到

　　R中即可

　　()動態申請R

　　實現時R是動態申請的因為申請的空間可能很大故須加入申請空間是否成功的處理

　　歸並算法

　　void Merge(SeqList Rint lowint mint high)

　　{//將兩個有序的子文件R[lowm)和R[m+high]歸並成一個有序的

　　//子文件R[lowhigh]

　　int i=lowj=m+p=; //置初始值

　　RecType *R; //R是局部向量若p定義為此類型指針速度更快

　　R=(ReeType *)malloc((highlow+)*sizeof(RecType));

　　if(! R) //申請空間失敗

　　Error(Insufficient memory available!);

　　while(i<=m&&j<=high) //兩子文件非空時取其小者輸出到R[p]上

　　R[p++]=(R[i]key<=R[j]key)?R[i++]R[j++];

　　while(i<=m) //若第個子文件非空則復制剩余記錄到R中

　　R[p++]=R[i++];

　　while(j<=high) //若第個子文件非空則復制剩余記錄到R中

　　R[p++]=R[j++];

　　for(p=i=low;i<=high;p++i++)

　　R[i]=R[p];//歸並完成後將結果復制回R[lowhigh]

　　} //Merge

From:http://tw.wingwit.com/Article/program/sjjg/201311/23778.html