【数据结构与算法】专题正在持续更新中，各种数据结构的创建原理与运用✨，经典算法的解析✨都在这儿，欢迎大家前往订阅本专题，获取更多详细信息哦
本系列专栏 – 数据结构与算法_勾栏听曲_0
欢迎大家 点赞 评论 收藏⭐️
个人主页 – 勾栏听曲_0的博客
希望本文能对你有所帮助，如有不足请指正，共同进步吧
一个人无论在祈祷什么，他祈祷的都只不过是一个奇迹。所有祈祷文无非都是一个意思:“伟大的上帝啊，请使二乘二不等于四吧!”
分治法
算法思想
时间效率分析
合并排序
分治法
算法思想
分治法可能是最著名的通用算法设计技术了。虽然它的名气可能和它那好记的名字有关，但它的确是当之无愧的:很多非常有效的算法实际上就是这个通用算法的特殊实现。其实，分治法是按照以下方案工作的。
(1)将一个问题划分为同一类型的若干子问题，子问题最好规模相同。
(2)对这些子问题求解(一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法)。
(3)有必要的话，合并这些子问题的解，以得到原始问题的答案。
分治法的流程可以参见下图，该图描述的是将一个问题划分为两个较小子问题的例子，也是最常见的情况(至少那些设计运行在单CPU机器上的分治算法是这样的)。
时间效率分析
在分治法最典型的运用中，问题规模为n的实例被划分为两个规模为n/2的实例。更一般的情况下，一个规模为n的实例可以划分为b个规模为n/b的实例，其中α个实例需要求解(这里，a和b是常量，a≥1，b>1)。为了简化分析，我们假设n是b的幂，对于算法的运行时间T(n)，我们有下列递推式:
T(n) =aT(n /b)+ f(n)
其中，f(n)是一个函数，表示将问题分解为小问题和将结果合并起来所消耗的时间(对于求和的例子来说，a = b = 2，f(n)= 1)。上述递推式被称为通用分治递推式(generaldivide-and-conquer recurrence)。显然，T(n)的增长次数取决于常量a和b的值以及函数f(n)的增长次数。在分析许多分治算法的效率时，可以应用下列定理来大大简化我们的工作。
主定理如果在递推式(5.1)中 f(n)e e(n*)，其中d≥0，那么
时，该问题的时间复杂度为n的d次方
当a =
当a >
接下来通过视频演示来了解合并排序算法对数列8,3,2,9,7,1,5,4进行排序的操作过程。
合并排序_分治法
代码实现：
#include void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* 创建临时数组 */ int L[n1], R[n2]; /* 复制数据到临时数组 arrays L[] 和 R[] */ for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; /* 归并临时数组到 arr[l..r]*/ i = 0; // 初始化第一个子数组的索引 j = 0; // 初始化第二个子数组的索引 k = l; // 初始归并子数组的索引 while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } /* 复制 L[] 的保留元素 */ while (i < n1) { arr[k] = L[i]; i++; k++; } /* 复制 R[] 的保留元素 */ while (j < n2) { arr[k] = R[j]; j++; k++; }} /* l 为左侧索引，r 为右侧索引 */void mergeSort(int arr[], int l, int r) { if (l < r) { // 求中间位置，防止 (l+r) 的和超过 int 类型最大值 int m = l+(r-l)/2; // 递归排序左半部分 mergeSort(arr, l, m); // 递归排序右半部分 mergeSort(arr, m+1, r); // 合并 merge(arr, l, m, r); }}
