分治算法 |
您所在的位置：网站首页 › 实现归并排序利用的算法设计思想是 › 分治算法 |
分治算法
|
分治算法-合并排序
合并排序概念合并排序图解算法分析算法代码实例代码分析
合并排序概念
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。 合并排序图解
算法有两大部分，第一部分就是分，第二部分就是治。 分就是把要排序的数据分成两部分，再把两部分分成四部分，最后分成单个。 治就是合并把单个数据合并成两个两个的有序数据，再把两个两个的有序数据合并成四个四个的有序数据，最终合并成一个我们想要的有序序列。 如上图的例子，首先递归把数据 分成单个，这个对我们来说不是问题，那么只要解决了把若干个有序的子序列合并为一个有序的序列，那么合并算法就完全理解了。 两个数字怎样合并成有序的序列呢，那就是比较两个 数字的大小，小得在前大的在后面，这样就得到了一个有序的序列，因此他们就是上图中绿色的第一行。 两个有序的子序列怎样合并成一个有序的序列呢，依然是比较大小，我们把两个序列并齐，分别从小的一头找到最小的数字，放在新序列的首位，重复这个过程就会得到一个新的有序的序列。这样就得到了上图绿色部分的三四行。 最终得到整个序列的有序序列。 算法代码实例输入十个数字，合并为一个有序的序列。 #include #include using namespace std; #define MAXSIZE 20 #define KeyType int typedef struct{ KeyType key; }RedType; typedef struct{ RedType r[MAXSIZE+1]; int length; }SqList; int enter(SqList &L){ L.length=0; cout for(int i=1 ; i if(R[i].key int mid=(low+high)/2; MSort(R,S,low,mid); MSort(R,S,mid+1,high); Merge(S,T,low,mid,high); } } void MergeSort(SqList &L){ MSort(L.r,L.r,1,L.length); } int main(){ SqList L; enter(L); print(L); MergeSort(L); cout RedType r[MAXSIZE+1]; int length; }SqList; int enter(SqList &L){ L.length=0; cout RedType S[MAXSIZE+1]; if(low==high) T[low]=R[low]; else{ int mid=(low+high)/2; MSort(R,S,low,mid); MSort(R,S,mid+1,high); Merge(S,T,low,mid,high); } }归并操作，把相邻的两个有序序列合并为一个有序序列 void Merge(RedType R[],RedType T[],int low,int mid,int high){ int i=low,j=mid+1,k=low; while(i |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |