Author: bakari Date: 2012.7.30
排序算法有很多种，每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为归并排序。
归并排序是分治法最好的应用，先将一个大的问题分解成小的问题，然后着重去解决小的问题，小问题一解决大问题也就自然而然地解决了。
所以分治法的具体思路就出来了：
将一个数组序列按分为两个序列，序列1和序列2 ，从首元素开始比较，小的元素插入到另一个容器，知道其中一个序列排列完，在把另外的序列插入到该容器的后面，但前提是两个序列事先应该排好序。排好一趟之后再扩大序列区间，随着小问题的解决，大问题也就解决了。
废话不多说，见代码：先看类的定义：
1 /*********************************************************** 2 * Author: bakari Date: 2012.7.30 3 * 合并排序 4 * 合并排序的宗旨是将两个已经排好序的序列重新归并为一个序列 5 * 算法的关键点就在于确定合并的基数，即每一次合并元素的数量 6 ***********************************************************/ 7 class MegerSort 8 { 9 int len; 10 vector<int> MegerList; 11 vector<int> ReplaceList; 12 public: 13 MegerSort(vector<int> _list,int len); 14 void Meger_Sort(int index); 15 void FindIndex(); 16 void Print(); 17 };
下一步需要找到分治的基数，就是序列区间的大小，从 1 开始，如下：
1 void MegerSort::FindIndex() 2 { 3 int ix = 1; 4 while(ix < len) 5 { 6 Meger_Sort(ix); 7 for (int i = 0; i != len;++i) 8 MegerList[i] = ReplaceList[i]; 9 ix = ix * 2; 10 } 11 12 }
下面就是排序的算法：
1 void MegerSort::Meger_Sort(int index) 2 { 3 int i1 = 0; //序列1的起始元素 4 int k = 0; 5 while(i1 + index <= len){ 6 7 int i2= i1 + index; //序列2的起始元素 8 int j1 = i2 - 1; //序列1的末端元素 9 int j2 = (i2 + index - 1) < (len -1) ? i2 + index -1 : len - 1; //序列2的末端位置 10 while (i1 <= j1 && i2 <= j2) 11 { 12 if (MegerList[i1] < MegerList[i2]) 13 ReplaceList[k++] = MegerList[i1++]; //将小的元素放入另一个容器 14 else ReplaceList[k++] = MegerList[i2++]; 15 } 16 if (i1 > j1) //如果序列1排列完 17 { 18 while (i2 <= j2) //进行序列2的排列 19 ReplaceList[k++] = MegerList[i2++]; 20 } 21 if (i2 > j2) //和上面相反 22 { 23 while (i1 <= j1) 24 ReplaceList[k++] = MegerList[i1++]; 25 } 26 i1 = j2 + 1; 27 } 28 }
