目录
前言
结合图文剖析归并排序的思路；学习分治法、递归思想、gap调整区间优化。
分治法（Divide and Conquer）：归并排序是一种分治算法，它将问题分解成多个小问题，解决这些小问题，然后将它们的解决方案组合起来解决原始问题。
递归（Recursion）：归并排序的实现通常依赖于递归，这是一种在函数内部调用自身的方法。递归是解决某些问题（如树的遍历、排序等）的强大工具。
稳定性（Stability）：归并排序是一种稳定的排序算法，这意味着相等的元素在排序后保持它们原始的相对顺序。这对于某些应用场景非常重要。
时间复杂度（Time Complexity）：归并排序的最坏、平均和最佳时间复杂度都是 O(nlogn)O(nlogn)，这使得它在大多数情况下都表现良好。
空间复杂度（Space Complexity）：归并排序需要 O(n)O(n) 的额外空间来存储合并过程中的临时数组，这可能限制了它在空间受限的环境中的使用。
算法效率（Algorithm Efficiency）：通过学习归并排序，您可以更好地理解不同排序算法的效率和适用场景。
代码实现：您将学会如何实现一个有效的归并排序算法，包括如何合并两个已排序的数组以及如何递归地分解和排序数组。
调试技巧（Debugging Skills）：在实现归并排序的过程中，您可能会遇到数组越界、栈溢出等错误，学习如何解决这些问题可以提高您的调试技能。
内存管理（Memory Management）：在非递归版本的归并排序中，您需要手动管理内存，包括分配和释放，这有助于您理解程序的内存使用情况。
优化（Optimization）：了解如何优化归并排序，比如在小数组中使用插入排序以减少递归调用的开销。
算法适用性（Algorithm Applicability）：知道何时使用归并排序是合适的，例如在大数据集排序或者需要稳定排序的场合。
并行计算（Parallel Computing）：归并排序可以很容易地并行化，因为它的分治结构天然适合多线程或多处理器系统。
一.方法一：归并排序
1.1 归并思路
1.1.1 递归(分解)
1.先递归(分解)，把问题分为子问题，
1.1.2 区间(排序)
2.把数组分割为不同区间（子问题）进行两区间排序
1.1.3 合并拷贝回原数组(合并)
把左右区间进行排序。注意：排序过程为：比较左右区间，排序好的先放入临时数组tmp中，再把数组tmp中的内容拷贝到原数组a中
二.归并排序过程
2.1 递归(分解)图解
//递归到最低层 if (left >= right) return; //[left,mid][mid+1,right]有序，则可以合并，现在无序，子问题解决 int mid = (left + right) / 2; MergeSort(a, left, mid, tmp); MergeSort(a, mid + 1, right, tmp);递归过程如下：
如上图中的left mid ,当left>=right 时(left左区间大于或等于right右区间，也就是递归分解到个元素)；此时我们分解已经为个元素了，接下来要做的事情是：归并[left,mid][mid+1,right]有序
2.2 归并有序区间(排序)图解
2.2.1 单独一趟排序
//归并[left,mid][mid+1,right]有序 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; }
编辑
注意：[left , mid] [mid+1 , right]
这两个区间有序时，才能进行归并。
而递归分解到不可再分时。也就是只有一个数时 ，认为它是有序的。
如：左区间为数字7 9，右区间为数字3 6 单独一趟归并排序后左右区间排序合并，2个区间变为1个区间且该合并后的区间数组内容为有序的，内容为 3 6 7 9 。递归返回时，该区间再与新的有序区间进行比较，能一直保证左右区间为有序状态，即满足归并排序的要求。
2.2.2 有序区间递归排序
那么递归排序(前面是单趟排序，这里是多趟排序)中，子问题解决后，递归返回
2.2.3 数组拷贝(合并)
//把数组tmp中的数据拷贝到原数组a中 for (int i = left; i <= right; i++) { a[i] = tmp[i]; }这里合并拷贝完，接着就会返回上一层调用。也就是接着处理上一层、左右区间排序好的、数据更多的有序子问题
2.3 归并全部代码
归并排序，采用分治法，这里的归并排序通过(分解、排序、合并)，不断解决子问题：进行排序也就是归并排序
void PrintfArr(int*a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void MergeSort(int*a, int left, int right, int*tmp) { //递归到最低层 if (left >= right) return; //[left,mid][mid+1,right]有序，则可以合并，现在无序，子问题解决 int mid = (left + right) / 2; MergeSort(a, left, mid, tmp); MergeSort(a, mid + 1, right, tmp); //归并[left,mid][mid+1,right]有序 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //把数组tmp中的数据拷贝到原数组a中 for (int i = left; i <= right; i++) { a[i] = tmp[i]; } } void TestMergeSort() { int a[] = { 3,4,2,1,5,7,8,9,4,67,2,4,9,0,10 }; PrintfArr(a, sizeof(a) / sizeof(a[0])); int* tmp = (int*)malloc(sizeof(int) * (sizeof(a) / sizeof(a[0]))); MergeSort(a, 0, sizeof(a) / sizeof(a[0])-1, tmp); PrintfArr(a, sizeof(a) / sizeof(a[0])); } int main() { TestMergeSort(); return 0; }
三.方法二：归并排序(非递归)
3.1 归并思路(非递归)
3.1.1 使用gap分割
使用gap进行数组的分割处理，
3.1.2 比较合并
这里需要注意
int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1;//[i, i + gap -1][i + gap, i + 2*gap - 1] //修正区间 1.只有一组： if (begin2 >= n) { break; } //修正区间 2.有两组：右边组没满 if (end2 >= n) { end2 = n - 1; }情况一：只有左边一组(begin2到end2没数据)不需要合并，使用break跳过
这里就不对数组中最后的元素3进行合并了，等到后面gap扩大再处理。
情况二：含两组数据[i, i + gap -1][i + gap, i + 2*gap - 1]但是右边区间数据没放满，需要修正区间
3.1.3 拷贝回原数组
把tmp数组中的内容拷贝回原数组中
3.2 归并过程(非递归)
3.2.1 多趟gap
使用多趟gap，对数组需要排序的内容进行调整，这里的gap=gap*2；使用gap的2倍增长模拟归并排序，这里就没有使用递归的方法了。仅仅是数组内存的操作。
void MergeSortNonR(int* a, int n, int* tmp) { int gap = 1; while (gap < n) { 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; //[i, i + gap -1][i + gap, i + 2*gap - 1] //修正区间 1.只有一组： if (begin2 >= n) { break; } //修正区间 2.有两组：右边组没满 if (end2 >= n) { end2 = n - 1; } MergeArr(a, begin1, end1, begin2, end2, tmp); } gap *= 2; } }
3.2.2 合并过程
通过左右区间进行比较，随着前面的gap的倍数增大，合并过程中的左右区间比较的范围也程倍数增长。2:2合成4 4:4合成8 8:8合成16.........若区间越界则需要处理。
MergeArr(int* a, int begin1, int end1, int begin2, int end2, int*tmp) { int index = begin1; int begin = begin1, end = end2; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //拷贝回原数组 for (int i = begin; i <= end; i++) { a[i] = tmp[i]; } }
3.3.3 归并(非递归)全部代码
归并排序(非递归全部代码)
void PrintfArry(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } MergeArr(int* a, int begin1, int end1, int begin2, int end2, int*tmp) { int index = begin1; int begin = begin1, end = end2; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //拷贝回原数组 for (int i = begin; i <= end; i++) { a[i] = tmp[i]; } } void MergeSortNonR(int* a, int n, int* tmp) { int gap = 1; while (gap < n) { 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; //[i, i + gap -1][i + gap, i + 2*gap - 1] //修正区间 1.只有一组： if (begin2 >= n) { break; } //修正区间 2.有两组：右边组没满 if (end2 >= n) { end2 = n - 1; } MergeArr(a, begin1, end1, begin2, end2, tmp); } gap *= 2; } } void TestMergeSortNonR() { int a[] = { 24,67,2,478,2,58,0,43,2,2,561,1,1,3,5,76 }; int* tmp = malloc(sizeof(int) * sizeof(a) / sizeof(a[0])); PrintfArry(a, sizeof(a) / sizeof(a[0])); if (tmp == NULL) printf("malloc error"); MergeSortNonR(a,sizeof(a)/sizeof(a[0]),tmp); PrintfArry(a, sizeof(a) / sizeof(a[0])); free(tmp); } int main() { TestMergeSortNonR(); return 0; }