分治算法一般分為如下3個(gè)步驟。

劃分問(wèn)題：把問(wèn)題的實(shí)例劃分成子問(wèn)題。
遞歸求解：遞歸解決子問(wèn)題。
合并問(wèn)題：合并子問(wèn)題的解得到原問(wèn)題的解。

歸并排序

按照分治三步法，對(duì)歸并排序算法介紹如下。
劃分問(wèn)題：把序列分成元素個(gè)數(shù)盡量相等的兩半。
遞歸求解：把兩半元素分別排序。
合并問(wèn)題：把兩個(gè)有序表合并成一個(gè)。

借鑒一下https://blog.csdn.net/yuehailin/article/details/68961304
的思想：

首先考慮下如何將將二個(gè)有序數(shù)列合并。這個(gè)非常簡(jiǎn)單，只要從比較二個(gè)數(shù)列的第一個(gè)數(shù)，誰(shuí)小就先取誰(shuí)，取了后就在對(duì)應(yīng)數(shù)列中刪除這個(gè)數(shù)。然后再進(jìn)行比較，如果有數(shù)列為空，那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可。

解決了上面的合并有序數(shù)列問(wèn)題，再來(lái)看歸并排序，其的基本思路就是將數(shù)組分成二組A，B，如果這二組組內(nèi)的數(shù)據(jù)都是有序的，那么就可以很方便的將這二組數(shù)據(jù)進(jìn)行排序。如何讓這二組組內(nèi)數(shù)據(jù)有序了？

可以將A，B組各自再分成二組。依次類推，當(dāng)分出來(lái)的小組只有一個(gè)數(shù)據(jù)時(shí)，可以認(rèn)為這個(gè)小組組內(nèi)已經(jīng)達(dá)到了有序，然后再合并相鄰的二個(gè)小組就可以了。這樣通過(guò)先遞歸的分解數(shù)列，再合并數(shù)列就完成了歸并排序。

更簡(jiǎn)潔的代碼：

#include<iostream> using namespace std; void merge_sort(int *a,int x,int y,int *t){if(y-x>1){int m=x+(y-x)/2;int p=x,q=m,i=x;merge_sort(a,x,m,t);merge_sort(a,m,y,t);while(p<m||q<y){if(q>=y||(p<m&&a[p]<=a[q]))t[i++]=a[p++];else t[i++]=a[q++];}for(int i=x;i<y;i++) a[i]=t[i];} } int main(){int a[100],b[100];for(int i=0;i<10;++i){cin>>a[i];}merge_sort(a,0,10,b);for(int i=0;i<10;++i){cout<<b[i]<<' ';} }

分析一下這個(gè)代碼的意思：
if(q>=y||(p < m && a[p] < =a[q]))
這個(gè)意思是說(shuō)，如果右邊的數(shù)組為空或者左邊數(shù)組不為空，而且左邊的數(shù)小于右邊，那么就把左邊的這個(gè)數(shù)放到臨時(shí)空間
整體上來(lái)說(shuō)，先遞歸成一個(gè)數(shù)，然后再進(jìn)行合并

總結(jié)

以上是生活随笔為你收集整理的（分治法）归并排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。