歸并排序算法算法思路：采用遞歸的方式將一串數(shù)組逐級劃分，直至不可分割時，此時順序唯一，將元素放回排序序列中。設(shè)置遞歸函數(shù)（Merge_Sort）那么遞歸中需要進行如下操作：（1）劃分數(shù)組，設(shè)定劃分區(qū)間這里我們向下取整（左序列短于右序列，另一種方式當然也是可以的）設(shè)數(shù)組起點為p,終點為r,則：令：q=（r+p-1）/2;（2）分別處理左右區(qū)間Merge_Sort（array[],p,q）;Merge_Sort（array[],q+1,r）;（3）合并左右兩個區(qū)間Merge（array[],p,q,r）;這里用到了一個歸并操作的函數(shù)，我們來簡單分析一下這個函數(shù)中需要處理的任務(wù)。首先：這個函數(shù)需要實現(xiàn)的功能為合并兩個排好順序的數(shù)組，這里簡單說明一下為什么是已經(jīng)排好順序的兩個數(shù)組，我們設(shè)想最簡單的情況，利用Merge_Sort（）函數(shù)進行逐級遞歸，當遞歸到左右區(qū)間都只剩一個的情況下，此時再對左右區(qū)間進行遞歸不再處理任何內(nèi)容，此時回到上層遞歸中，這時候函數(shù)就第一次行進到Merge（涵數(shù)，此時需要對這兩個都只有一

個數(shù)當然是算是已經(jīng)排好序的數(shù)組進行排序，那么就得到了包含這兩個數(shù)的一個次小有序數(shù)組。按這種邏輯可推知每次執(zhí)行Merge（）時，左右兩個數(shù)組都是有序數(shù)組。那么我們在Merge（）內(nèi)的任務(wù)就是歸并兩個有序數(shù)組，并且令歸并后的數(shù)組有序。下面用一張圖來說明：假設(shè)我們要排列這樣一個數(shù)組[1,3,7,9,2,4,6,8];從上圖中分析我們可以知道，在函數(shù)中我們需要進行如下處理：（1）劃分數(shù)組，元素個數(shù)分別為：n1=q-p+1;n2=r-q;分別申請兩個動態(tài)數(shù)組L,R需比其中元素個數(shù)多1用于存放一個極大值。分別進行賦值：fromi=0ton1-1L[i]=array[p+i];Fromj=0ton2-1;R[j]=array[q+j+1];L(n1)=inf;R(n2)=inf;I=0;j=0;歸并操作fromk=ptorifL(i)<R(j);array[k]=L[i];i++;elsearray[k]=R[j];j++;代碼實現(xiàn)(C語言)：#include<stdio.h>#include<stdlib.h>#defineINF65535voidMerge(intarray[],intp,intq,intr)(intn1=q-p+1;intn2=r-q;inti,j,k;int*L=malloc(sizeof(int)*(n1+1));int*R=malloc(sizeof(int)*(n2+1));for(i=0;i<n1;i++)L[i]=array[p+i];for(j=0;j<n2;j++)R[j]=array[q+j+1];L[n1]=INF;R[n2]=INF;i=0;j=0;for(k=p;k<=r;k++)(if(L[i]<R[j])(array[k]=L[i];i++;)else(array[k]=R[j];j++;)voidMerge_Sort(intarray[],intp,intr)(intq；if(p<r)(q=(r+p-1)/2;Merge_Sort(array,p,q);Merge_Sort(array,q+1,r);Merge(array,p,q,r);))intmain()(inti;intarray[10]=(1,3,7,5,4,2,6,9,5,8);printf("MergeSortExample\n");printf("Beforesort:\n");for(i=0;i<10;i++)printf("%d",array[i]);printf("\n");Merge_Sort(array,0,9);pri