归并排序算法(mergesort)是将一个序列划分为同样大小的两个子序列，然后对两个子序列分别进行排序，最后进行合并操作，将两个子序列合成有序的序列。在合成的过程中，一般的实现都需要开辟一块与原序列大小相同的空间，以进行合并操作。这里介绍一种不需要开辟新的空间就可以进行归并操作的原地归并算法。代码来说事儿：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | template <class T> void Swap(T& l, T& r) //~ 交换 { T t = l; l = r; r = t; } template <class T> void Reverse(T* v, size_t size) //~ 反序 { size--; size_t l = 0; while(l < size) { Swap(v[l++], v[size--]); } } template <class T> void Exchange(T* v, size_t l, size_t s) //~ 分块交换：前l个与s-l交换 { //~ 据说叫手摇算法？ if(l == 0 || s == 0) return ; Reverse(v, l); Reverse(v+l, s - l); Reverse(v, s); } template <class T> void merge(T* v, size_t size) { if(size == 1) //~ 递归终结点1 return ; else if(size == 2) //~ 递归终结点2 { if(v[0] > v[1]) Swap(v[0], v[1]); } else { //~ 分别排序 merge(v, size/2); merge(v+size/2, size-size/2); size_t l = 0, r = size/2; //~ 原地归并 while(l < r && r < size) //~ 核心算法 { while(v[l] <= v[r] && l < r) ++l; //~ 找到左面第一个比v[r]大的v[l] size_t to_mv = 0; //~ 计数器 while(v[r] < v[l] && r < size) ++r, ++to_mv; //~ 右侧找到to_mv个比v[l]小的数 Exchange(v+l, r-l-to_mv, r-l);//~ 将此to_mv个数移到v[l]前面 l += to_mv; //~ 改变l，继续下一轮循环 }//~ l >-r 或者 r >= size时归并结束 } } |
你好！除了代码，此处没有多少原创之物，皆为本人搜集、整理、总结之记录与心得，欢迎转载分享！转载时请尽量注明出处，将不胜感激。祝你健康、快乐！
楼主你这个算法的复杂度是O(n^2)的，。。考虑如下case：
前半部分：1 3 5 7 9 11 13 15
后半部分：2 4 6 8 10 12 14 16