1、归并排序
1.1 算法思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
如果说快速排序是前序遍历，那么归并恰巧就是它的对立面，归并排序相当于是二叉树的后序遍历
归并排序算法思想(排升序为例)：
1.假设数组有N个元素,先将数组不断地二分,直到将数组划分为N个由单个元素构成的子数组,整个划分过程中所有子数组构成满二叉树(或接近满二叉树)的逻辑结构,如图:
2.数组划分完后再逐层向上将二叉树兄弟结点子数组(具有相同前驱结构)两两进行归并操作完成排序:
归并排序是将区间逐个分解为一个个小区间，直到不能分割为止，然后一步步 归并起来 ，逐层返回。而这一过程需要借助一个辅助数组 tmp 来完成归并过程。
eg.两个有序数组归并：依次比小，小的尾插到新空间
1.2 两个有序子序的归并(排升序)
arr是被分割的原数组,tmp是用于归并操作的临时数组,begin是arr的左端下标,end是arr的右端下标
假设数组arr被二等分为两个子序列(两个子序列都是有序的):
接下来我们将上图中的[begin,(begin+end)/2)和[(begin+end)/2),end)两个子序列(有序)合并到一个tmp数组中构成一个新的有序序列（通过三指针完成）
代码：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end)//不存在返回 { return; } int mid = (begin + end) >> 1;// /2 //[begin,mid] [mid+1,end]归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; /* * 第一种拷贝回原数组的方式 - memset * 此种做法 cnt 从 begin 开始 * memset 从 begin 位置开始，一共拷贝 end - begin + 1 个元素 * 和下面做法道理相同 */ // int cnt = begin; /* * 第二种拷贝回原数组的方式 - 循环拷贝 * 此种做法 cnt 从 0 开始 * 开始拷贝的位置从 begin 开始 * cnt 最终的长度就是 [begin, end] 之间的长度 * 没问题 */ int cnt = 0; while (begin1 <= end1 && begin2 <= end2) { // 保持稳定性 if (a[begin1] <= a[begin2]) { tmp[cnt++] = a[begin1++]; } else { tmp[cnt++] = a[begin2++]; } } while (begin1 <= end1) { tmp[cnt++] = a[begin1++]; } while (begin2 <= end2) { tmp[cnt++] = a[begin2++]; } // 方法1 // memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); //目标 源 大小 // 方法2 for (int i = begin, j = 0; i <= end; i++, j++) { a[i] = tmp[j]; } }
1.3 归并递归版本
完成arr数组[left,right)区间序列排序的过程可以拆分为如下三个步骤:
1.先完成左子区间[left,left + (right - left) / 2)的排序
2.再完成右子区间[left + (right - left) / 2,right)的排序
3.最后将左右子区间进行归并完成[left,right)区间序列的排序
数组二分的递归框架：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end)//不存在返回 { return; } int mid = (begin + end) >> 1;// /2 //[begin,mid] [mid+1,end] 子区间递归排序 // 递归到底部 _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); }
思路：
1.对于归并排序来说，首先开辟一个辅助数组 tmp 。我们每一次取一个中间点 mid=(begin + end)/2 。
2.按照后序遍历的方式，分别递归左右区间：[begin,mid] ，[mid+1,end] 一直递归到底部，递归的返回条件为begin>=end 。
3.然后归并，设定相关变量，将两区间内对应元素由小到大放置到tmp 数组对应位置处。
4.如果放置过程结束，一个数组没有放置完，则需要在循环结束后，将数组的数据全部倒入 tmp 数组中。
5.在上面的过程完毕之后，再把tmp 数组中的数据拷贝回原数组。
6.最终，递归逐层返回后，就完成了归并过程。
代码：
//子函数 void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end)//不存在返回 { return; } int mid = (begin + end) >> 1;// /2 //[begin,mid] [mid+1,end] 子区间递归排序 // 递归到底部 _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); //[begin,mid] [mid+1,end]归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; /* * 第一种拷贝回原数组的方式 - memset * 此种做法 cnt 从 begin 开始 * memset 从 begin 位置开始，一共拷贝 end - begin + 1 个元素 * 和下面做法道理相同 */ // int cnt = begin; /* * 第二种拷贝回原数组的方式 - 循环拷贝 * 此种做法 cnt 从 0 开始 * 开始拷贝的位置从 begin 开始 * cnt 最终的长度就是 [begin, end] 之间的长度 * 没问题 */ int cnt = 0; while (begin1 <= end1 && begin2 <= end2) { // 保持稳定性 if (a[begin1] <= a[begin2]) { tmp[cnt++] = a[begin1++]; } else { tmp[cnt++] = a[begin2++]; } } while (begin1 <= end1) { tmp[cnt++] = a[begin1++]; } while (begin2 <= end2) { tmp[cnt++] = a[begin2++]; } // 方法1 // memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); //目标 源 大小 // 方法2 for (int i = begin, j = 0; i <= end; i++, j++) { a[i] = tmp[j]; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("mallol fail"); return; } _MergeSort(a, 0, n - 1, tmp); }
1.4 归并排序非递归版本
归并排序的非递归版本在这一块是一个难点，因为它本身就很难想到。
首先想一下，对于归并排序来说，能不能像快速排序那样借助数据结构-栈来实现？
如果用栈，是不太行的。因为归并是一种类似二叉树后序遍历的排序，当将区间入栈后，把区间拿出来处理，之后要继续分割时，一段区间可能就不见了，所以借助数据结构-栈时不太行的。
所以我们可以不借助数据结构，用一种相对简单的方法完成。
我们可以设定一个 gap ，控制我们的区间大小，gap 就是归并时每组的数据个数。由于我们是类似二叉树后序遍历的方式，所以我们一开始的归并实际上就是 gap 为 1 情况。
如下图：
arr代表待排序的数组,size为待排序数组的元素个数
通过每次改变gap 实际上也就是改变了区间大小，就模拟除了归并递归到底，从小区间合并逐渐到大区间合并的过程。所以我们就让gap 每次 × 2，这样子就是归并每次扩大区间的过程。
使用一个变量i来遍历每一个gap情形下的各个进行归并的序列组(每个序列组由两个子数组构成):
for (int gap = 1; gap < size; gap *= 2) //完成logN个层次的子数组的归并 { for (int i = 0; i < size; i += 2 * gap) //i每次跳过一个归并序列组(每个序列组有两个子数组) { //对子数组[i,i+gap-1]和子数组[i+gap,i+2*gap-1]进行归并操作 } }
但是上面的方法只能解决数组长度恰巧被整除的情况，对于无法被整除的情况可能就会造成越界。比如 n=17 。在gap=4 时，最后一段区间 [ 17 , 20 ] 越界，所以这里需要调整
我们设置四个点begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + 2 * gap - 1四个点来规定两段区间。
列举一下，这四个点的越界情况，我们可以分为三种情况：
1 .end1, begin2, end2越界
2.end1没有越界,begin2,end2 越界
3.end2 越界
以上是三种越界情况，需要分别处理，处理方式分为 修正区间 和 不修正区间 ：
修正区间 ：
第一种越界情况，实际上就是 end1≥n ，那么这种情况修正区间的话，这时将end1=n−1 ，之后将没有越界的部分拷贝到 tmp 数组中，然后将[begin2,end2] 修正为一个不存在的区间，这样就不会进入后面循环，也就不会拷贝进数据。
反例：如果begin2 =end2 = n - 1，就会出现有一个数据重复归并的bug
if (end1 >= n) { end1 = n - 1; // begin2 和 end2 修正为不存在的区间 begin2 = n; end2 = n - 1; }
第二种越界情况，就是 begin2≥n ，这种情况下直接将[begin2,end2] 修正为不存在的区间即可。
else if (begin2 >= n) { begin2 = n; end2 = n - 1; }
第三种越界情况，就是end2≥n，这种情况将end2=n−1 ，让两端区间正常归并。
else if (end2 >= n) { end2 = n - 1; }
这种情况可以边归并边拷贝，也可以一组归并完了拷贝。
循环外拷贝，修正区间后，直接一把全部拷贝：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int gap = 1; while (gap < n) { // 一组归并的跨距为 2 * gap for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; int j = i; // 修正区间 if (end1 >= n) { end1 = n - 1; // begin2 和 end2 修正为不存在的区间 begin2 = n; end2 = n - 1; } else if (begin2 >= n) { begin2 = n; end2 = n - 1; } else if (end2 >= n) { end2 = n - 1; } //归并 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } //拷贝 while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } // 可以局部拷贝 //memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } memcpy(a, tmp, sizeof(int) * n); gap *= 2; } free(tmp); tmp = NULL; }
