分治法的基本概念、思想
分治法是一种很重要的算法。
字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
不难发现,分治法的思想与递归极其类似。实际上,分治与递归确实是密不可分。
分治法的策略
将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破。
分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模1较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,最后将各子问题的解合并得到原问题的解。
分治法适用的情况
分治法所能解决的问题一般具有以下几个特征:
- 可分:该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
- 可治:该问题的规模缩小到一定的程度就可以容易地解决
- 可合并:利用该问题分解出的子问题的解可以合并为该问题的解
- 不重复:该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题
分治法的基本步骤
分治法在每一层递归上都有三个步骤:step1
分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;step2
解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题step3
合并:将各个子问题的解合并为原问题的解
分治实例 —— 归并排序(MERGE-SORT)
归并排序是利用分治的思想实现的排序方法,该算法采用经典的分治策略,将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案修补在一起,从而完成分而治之。
合并过程图解:
以4、5、7、8、1、2、3、6为例
-
首先开一个临时的数组temp,然后定义两个指针
i、j
,分别指向需要合并的一段序列的首元素,然后比较两个指针指向的元素,将较小的那个存入temp数组之中,再将其对应的指针右移。 -
继续比较两个指针指向的元素,仍然将较小的那个存入temp数组之中,再将其对应的指针右移。
-
继续比较两个指针指向的元素,还是将较小的那个存入temp数组之中,再将其对应的指针右移。
-
反复执行以上操作,比较两个指针指向的元素,将较小的那个存入temp数组之中,再将其对应的指针右移。
-
继续以上步骤
-
此时7 > 6,故将元素6存入temp数组之中,且
j
指针无法再往右移动,故将7、8整体移入数组中即可
当temp数组存储完所有元素之后,将其赋值给原数组即可。
比较归并排序与快速排序,会发现归并排序需要开一个额外的数组temp用来存储排好序的元素
归并排序模板
#include <iostream>
using namespace std;
const int N = 10010;
int num[N];//原数组
int tem[N];//临时数组
void merge(int low,int mid,int high)//合并函数
{
int i = low,j = mid + 1,k = low;//i、j指向需要合并的两个序列的首位置
while (i <= mid && j <= high)//i、j指针都不超过合并序列的最后位置
{
//将较小数存储在temp之中,并且后移指针
if (num[i] < num[j]) tem[k++] = num[i++];
else tem[k++] = num[j++];
}
while (i <= mid) tem[k++] = num[i++];//左半序列还有元素
while (j <= high) tem[k++] = num[j++];//右半序列还有元素
for (int i = low;i <= high;i++) num[i] = tem[i];//拷贝元素
}
void merge_sort(int l,int r)//递归设计:排序函数
{
if (l >= r) return;//递归出口:分解至一个数
int mid = (l + r) / 2;
merge_sort(l,mid);//归并排序左半序列
merge_sort(mid + 1,r);//归并排序右半序列
merge(l,mid,r);//将左右合并
}
int main()
{
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> num[i];
merge_sort(1,n);//对第1个位置到第n个位置进行归并排序
for (int i = 1;i <= n;i++) cout << num[i] << " ";
return 0;
}
分治实例 —— 快速排序
基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
实现原理文章来源:https://www.toymoban.com/news/detail-438216.html
- 设置两个变量
i、j
,排序开始时:i = 1,j = n
- 找基准位置,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面,默认序列的第一个数为基准元素,假设为
key
,先j
从右往左试探,直到a[j] < key
就停止试探,i
从左往右试探,直到a[i] > key
就停止试探,如果i < j
,就交换a[j]
与a[i]
;如果i与j相遇,则i或j上的元素与基准元素交换,则这一轮排序结束。此时,基准元素将序列一分为二 - 递归调用分界点前和分界点后的子数组排序,重复2.2、2.3的步骤
- 最终就会得到排序好的数组
例如:6,2,7,3,9,8对这6个数进行从小到大排序文章来源地址https://www.toymoban.com/news/detail-438216.html
- 初始时,设数组的第一个元素6为基准,用
i
指向数组首元素,用j
指向数组的最后一个元素,开始扫描。指针j
从后往前扫描,直到扫描到一个小于基准6的元素之后,停下。指针i
从前往后扫描,直到扫描到一个大于基准6的元素之后,停下。 - 在达到上图状态的时候,交换元素位置。
-
j
指针继续向左试探,然后指针i、j
相遇,此时,交换i、j
指向的元素与基准元素的位置.至此,第一趟排序结束。基准6左边的元素均小于6,右边的元素均大于6 - 对上图中元素6左边的部分进行快速排序。首先指针
i
指向3,指针j
指向2,j
先从右往左试探,会发现2 < 3,故直接停下。然后i
从左往右试探,发现i、j
指针重合。故交换元素位置,如下图。 - 同理,再对6右边的部分快速排序。首先指针
i
指向7,指针j
指向8,j
先从右往左试探,查到比7小的元素,一直走到7的位置停下。发现i、j
指针重合。故下一步继续快速排序9、8两个元素。最后得到一个递增序列。
快速排序模板
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[N];
int n;
void quick_sort(int l,int r)
{
if (l >= r) return;
int temp = a[l];//保存基准
int i = l,j = r;
while (i != j)
{
while (a[j] >= temp && i < j) j--;//j指针从右往左试探
while (a[i] <= temp && i < j) i++;//i指针从左往右试探
if (i < j) swap(a[i],a[j]);//当i、j指针都停下后,交换元素位置
}
a[l] = a[i];//i == j退出循环,与基准元素交换位置
a[i] = temp;//第一次快排结束,基准元素更新为temp,基准位置更新为i,再继续排序
quick_sort(l,i - 1);//对基准左边快速排序
quick_sort(i + 1,r);//对基准右边快速排序
}
int main()
{
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
quick_sort(1,n);//对第1个元素到第n个元素进行排序
for (int i = 1;i <= n;i++) cout << a[i] << " ";
return 0;
}
快速排序的时间复杂度
- 最好情况:发生在整个数组被分成两段长度相等的子数组时,为O(nlogn)
- 最坏情况:待排序的序列为正序或者逆序(9、8、7、6、5、4、3…),每次划分只得到一个比上一次划分少一个记录的子序列,为O(n ^ 2)
- 平均时间复杂度:O(nlogn)
到了这里,关于算法基础15 —— 分治算法(归并排序 + 快速排序)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!