超詳細(xì)解析C++實現(xiàn)歸并排序算法

第超詳細(xì)解析C++實現(xiàn)歸并排序算法目錄一、前言分治算法分治算法解題方法二、歸并排序1.問題分析2.算法設(shè)計3.算法分析三、AC代碼

一、前言

分治算法

歸并排序，其實就是一種分治算法，那么在了解歸并排序之前，我們先來看看什么是分治算法。在算法設(shè)計中，我們引入分而治之的策略，稱為分治算法，其本質(zhì)就是將一個大規(guī)模的問題分解為若干個規(guī)模較小的相同子問題，分而治之。

分治算法解題方法

1.分解：

將要解決的問題分解為若干個規(guī)模較小、相互獨立、與原問題形式相同的子問題。

2.治理：

求解各個子問題。由于各個子問題與原問題形式相同，只是規(guī)模較小而已，而當(dāng)子問題劃分得足夠小時，就可以用簡單的方法解決。

3.合并

按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。

二、歸并排序

1.問題分析

歸并排序是比較穩(wěn)定的排序方法。它的基本思想是把待排序的元素分解成兩個規(guī)模大致相等的子序列。如果不易分解，將得到的子序列繼續(xù)分解，直到子序列中包含的元素個數(shù)為1。因為單個元素的序列本身就是有序的，此時便可以進(jìn)行合并，從而得到一個完整的有序序列。

2.算法設(shè)計

（1）分解：

將待排序的元素分成大小大致一樣的兩個子序列。

（2）治理：

對兩個子序列進(jìn)行個并排序。

（3）合并：

將排好序的有序子序列進(jìn)行合并，得到最終的有序序列。

3.算法分析

首先我們先給定一個無序的數(shù)列（42，15，20，6，8，38，50，12），我們進(jìn)行合并排序數(shù)列，如下圖流程圖所示：

步驟一：首先將待排序的元素分成大小大致相同的兩個序列。

步驟二：再把子序列分成大小大致相同的兩個子序列。

步驟三：如此下去，直到分解成一個元素停止，這時含有一個元素的子序列都是有序的。

步驟四：進(jìn)行合并操作，將兩個有序的子序列合并為一個有序序列，如此下去，直到所有的元素都合并為一個有序序列。

舉例，下面我將以序列（4，9，15，24，30，2，6，18，20）進(jìn)行圖解。

（1）初始化：i=low，j=mid+1，mid=(low+hight)/2，申請一個輔助數(shù)組b

int*b=newint[hight-low+1];//用new申請一個輔助函數(shù)

inti=low,j=mid+1,k=0;//k為b數(shù)組的小標(biāo)

（2）現(xiàn)在比較a[i]和b[j]，將較小的元素放在b數(shù)組中，相應(yīng)的指針向后移動，直到imid或者jhight時結(jié)束。

while(i=midj=hight)

if(a[i]=a[j])

b[k++]=a[i++];//按從小到大存放在b數(shù)組里面

else

b[k++]=a[j++];

}

進(jìn)行第一次比較a[i]=4和a[j]=2，將較小的元素2放入數(shù)組b中，j++,k++，如下圖：

進(jìn)行第二次比較a[i]=4和a[j]=6，將較小的元素放4入數(shù)組b中，i++,k++，如下圖：

進(jìn)行第三次比較a[i]=9和a[j]=6，將較小的元素放6入數(shù)組b中，j++,k++，如下圖：

進(jìn)行第四次比較a[i]=9和a[j]=18，將較小的元素放9入數(shù)組b中，i++,k++，如下圖：

進(jìn)行第五次比較a[i]=15和a[j]=18，將較小的元素放15入數(shù)組b中，i++,k++，如下圖：

進(jìn)行第六次比較a[i]=24和a[j]=18，將較小的元素放18入數(shù)組b中，j++,k++，如下圖：

進(jìn)行第七次比較a[i]=24和a[j]=20，將較小的元素放20入數(shù)組b中，j++,k++，如下圖：

此時，jhight了，while循環(huán)結(jié)束，但a數(shù)組還剩下元素（imid）可直接放入b數(shù)組就可以了。如下圖所示：

while(i=mid)//j序列結(jié)束，將剩余的i序列補充在b數(shù)組中

b[k++]=a[i++];

while(j=hight)//i序列結(jié)束，將剩余的j序列補充在b數(shù)組中

b[k++]=a[j++];

}

現(xiàn)在將b數(shù)組的元素賦值給a數(shù)組，再將b數(shù)組銷毀，即可。

for(inti=low;i=hight;i++)//將b數(shù)組的值傳遞給數(shù)組a

a[i]=b[k++];

delete[]b;//輔助數(shù)組用完后，將其的空間進(jìn)行釋放（銷毀）

（3）遞歸的形式進(jìn)行歸并排序

voidmergesort(int*a,intlow,inthight)//歸并排序

if(lowhight)

intmid=(low+hight)/2;

mergesort(a,low,mid);//對a[low,mid]進(jìn)行排序

mergesort(a,mid+1,hight);//對a[mid+1,hight]進(jìn)行排序

merge(a,low,mid,hight);//進(jìn)行合并操作

}

三、AC代碼

#includestdio.h

#includeiostream

#includealgorithm

#includecstdlib

#includecmath

usingnamespacestd;

voidmerge(int*a,intlow,intmid,inthight)//合并函數(shù)

int*b=newint[hight-low+1];//用new申請一個輔助函數(shù)

inti=low,j=mid+1,k=0;//k為b數(shù)組的小標(biāo)

while(i=midj=hight)

if(a[i]=a[j])

b[k++]=a[i++];//按從小到大存放在b數(shù)組里面

else

b[k++]=a[j++];

while(i=mid)//j序列結(jié)束，將剩余的i序列補充在b數(shù)組中

b[k++]=a[i++];

while(j=hight)//i序列結(jié)束，將剩余的j序列補充在b數(shù)組中

b[k++]=a[j++];

k=0;//從小標(biāo)為0開始傳送

for(inti=low;i=hight;i++)//將b數(shù)組的值傳遞給數(shù)組a

a[i]=b[k++];

delete[]b;//輔助數(shù)組用完后，將其的空間進(jìn)行釋放（銷毀）

voidmergesort(int*a,intlow,inthight)//歸并排序

if(lowhight)

intmid=(low+hight)/2;

mergesort(a,low,mid);//對a[low,mid]進(jìn)行排序

mergesort(a,mid+1,hight);//對a[mid+1,hight]進(jìn)行排序

merge(a,low,mid,hight);//進(jìn)行合并操作

intmain()

intn,a[100];

cout"請輸入數(shù)列中的元素個數(shù)n為："endl;

cinn;

cout"請依次輸入數(shù)列中的元素："endl;

for(inti=0;ii++)

cina[i];