思路分析

• 什么是归并？

  • 示例：（归并后的结果copy到原数组）
    
  • 逻辑：
    if (a[begin1] <= a[begin2])
{tmp[i++] = a[begin1++];}
else
{tmp[i++] = a[begin2++];}
    

• 归并排序
  
  分解到“有序”再归并

递归

• int middle = (left + right) / 2;
• [left, middle]→[begin1,end1] ； [middle+1,right]→[begin2,end2]
• [begin1,end1]→左区间 [begin2,end2]→ 右区间
  （从处理顺序来看，归并排序相当于后序遍历二叉树-左右根，快速排序相当于前序遍历二叉树-根左右）
• 开辟空间后记得free❗

// 归并排序递归实现
void _MergeSort(int* a, int left, int right, int* tmp)
{assert(a && tmp);if (left == right)return;int middle = (left + right) / 2;//[left,  middle] [middle+1,right]//[begin1,end1]   [begin2,end2]int begin1 = left, end1 = middle, begin2 = middle + 1, end2 = right;//递归分解_MergeSort(a, begin1, end1, tmp);_MergeSort(a, begin2, end2, tmp);//mergeint i = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)
{assert(a);int* tmp = (int*)malloc(sizeof(int) * n);if (!tmp){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

迭代

• range=1（一个数与一个数归并）可以清楚地看到每组归并间隔两倍 range ：

• for (int i = 0; i < n; i += 2 * range)
  

• range=2（两个数与两个数归并）
  
  通过以上两个示例，不难得出：

• int begin1 = i, end1 = i + range - 1;

• int begin2 = i + range, end2 = i + 2 * range - 1;

• ⭐越界的问题！（修改）

• 由上可知，begin1<end1<begin2<end2

  • begin1越界 - 正好结束
  • end1越界：修改end1、begin2、end2的值，并使[begin2,end2]→ 右区间不存在（begin2 > end2）
  • begin2越界：修改begin2、end2的值，并使[begin2,end2]→ 右区间不存在（begin2 > end2）
  • end2越界：修改end2的值

• 或者也可以选择跳出循环，不处理剩下的数，直接copy

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{assert(a);int* tmp = (int*)malloc(sizeof(int) * n);if (!tmp){perror("malloc fail");exit(-1);}int range = 1;while (range < n){for (int i = 0; i < n; i += 2 * range){int begin1 = i, end1 = i + range - 1;int begin2 = i + range, end2 = i + 2 * range - 1;int j = begin1;//越界if (end1 >= n){end1 = n - 1;begin2 = end2 + 1;//begin2 > end2;}else if (begin2 == n){begin2 = end2 + 1;//begin2 > end2;}else if (end2 >= n){end2 = n - 1;}//mergewhile (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, tmp, sizeof(int) * n);range *= 2;}free(tmp);tmp = NULL;
}

代码汇总

// 归并排序递归实现
void _MergeSort(int* a, int left, int right, int* tmp)
{assert(a && tmp);if (left == right)return;int middle = (left + right) / 2;//[left,  middle] [middle+1,right]//[begin1,end1]   [begin2,end2]int begin1 = left, end1 = middle, begin2 = middle + 1, end2 = right;//递归分解_MergeSort(a, begin1, end1, tmp);_MergeSort(a, begin2, end2, tmp);//mergeint i = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)
{assert(a);int* tmp = (int*)malloc(sizeof(int) * n);if (!tmp){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{assert(a);int* tmp = (int*)malloc(sizeof(int) * n);if (!tmp){perror("malloc fail");exit(-1);}int range = 1;while (range < n){for (int i = 0; i < n; i += 2 * range){int begin1 = i, end1 = i + range - 1;int begin2 = i + range, end2 = i + 2 * range - 1;int j = begin1;//越界//end1越界if (end1 >= n){end1 = n - 1;begin2 = end2 + 1;//begin2 > end2;}else if (begin2 == n){begin2 = end2 + 1;//begin2 > end2;}else if (end2 >= n){end2 = n - 1;}//mergewhile (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, tmp, sizeof(int) * n);range *= 2;}free(tmp);tmp = NULL;
}