算法设计与分析基础之分治法,详解二分查找、合并以及快速排序

算法设计与分析基础之分治法,详解二分查找、合并以及快速排序_第1张图片

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关:问题的规模越小,越容易直接求解。 要想直接解决一个规模较大的问题,有时是很困难的。那么,为了更好地解决这些规模较大的问题,分治法应运而生了。 在计算机科学中,分治法是一种很重要的算法。它采取各个击破的技巧来解决一个规模较大的问题,该技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)等。话不多说,直接上案例。


目录

二分查找

问题描述

算法思想

构造实例

实现方法

1、两种非递归

2、递归算法

时间复杂度

二、合并排序

算法思想

合并方法

算法描述

非递归形式

递归形式

时间复杂度

三、快速排序

算法思想

快排分治体现

划分方法的构造实例

图示助理解

具体代码实现

运行效果

时间复杂度

 结语


二分查找

问题描述

二分查找又称为折半查找,它要求待查找的数据元素必须是按关键字大小有序排列的。给定已排好序的n个元素s1,…,sn,现要在这n个元素中找出一特定元素x。 首先较容易想到使用顺序查找方法,逐个比较s1,…,sn,直至找出元素x或搜索遍整个序列后确定x不在其中。显然,该方法没有很好地利用n个元素已排好序这个条件。因此,在最坏情况下,顺序查找方法需要O(n)次比较。

算法思想

假定元素序列已经由小到大排好序,将有序序列分成规模大致相等的两部分,然后取中间元素与特定查找元素x进行比较,如果x等于中间元素,则算法终止;如果x小于中间元素,则在序列的左半部继续查找,即在序列的左半部重复分解和治理操作;否则,在序列的右半部继续查找,即在序列的右半部重复分解和治理操作。可见,二分查找算法重复利用了元素间的次序关系。

构造实例

算法设计与分析基础之分治法,详解二分查找、合并以及快速排序_第2张图片

创建数组并随机赋值,定义low为数组左边界high为数组右边界(数组长度-1)middle为数组长度的一半。middle=(low+high)/2,即指示中间元素;我们需要通过代码来每次折半查找我们需要的元素值。

实现方法

1、两种非递归

twoFind1()

int twoFind1(int A[], int len, int K)
{
	int low = 0, high = len - 1,middle;
	if (low > high) return -2;
	while (low <= high)//包含等于的情况
	{
		middle = (low + high) / 2;
		if (K == A[middle]) return middle;
		else if (K > A[middle]) low = middle + 1;
		else high = middle - 1;
	}
	return -1;
}

twoFind2()

int twoFind2(int A[], int len, int K)
{
	int low = 0, high = len - 1,middle;
	if (low > high) return -2;
	while (low < high)//不含等于的情况,并在最后做判断
	{
		middle = (low + high) / 2;
		if (K == A[middle]) return middle;
		else if (K > A[middle]) low = middle + 1;
		else high = middle - 1;
	}
	if (low == high && A[low] == K) return low;
	return -1;
}

2、递归算法

//递归二分查找算法
int twoFind3(int A[], int k, int low, int high)
{
	int middle;
	if (low > high) return -1;//递归结束条件
	middle = (low + high) / 2;
	if (low==high && A[middle] == k) return middle;
	if (low < high) {
		if (A[middle] < k)      return  twoFind3(A, k, middle + 1, high);
		else  if(A[middle]==k)  return middle;
		else                    return  twoFind3(A, k, 0, middle - 1);
	}
	return -1;
}

 时间复杂度

算法设计与分析基础之分治法,详解二分查找、合并以及快速排序_第3张图片

二、合并排序

算法思想

合并排序是采用分治策略实现对n个元素进行排序的算法,是分治法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略,其计算过程分为三大步: (1)分解:将待排序元素分成大小大致相同的两个子序列。 (2)求解子问题:用合并排序法分别对两个子序列递归地进行排序。 (3)合并:将排好序的有序子序列进行合并,得到符合要求的有序序列。

合并方法

设置三个工作指针i,j,k。其中,i和j指示两个待排序序列中当前需比较的元素,k指向辅助数组B中待放置元素的位置。比较A[i]和A[j]的大小关系,如果A[i]小于等于A[j],则B[k]=A[i],同时将指针i和k分别推进一步;反之,B[k]=A[j],同时将指针j和k分别推进一步。如此反复,直到其中一个序列为空。最后,将非空序列中的剩余元素按原次序全部放到辅助数组B的尾部。 

 算法描述

非递归形式

void Merge(int A[],int low,int middle,int high)
{
int i,j,k; 
int *B=new int[high-low+1];
i=low; j=middle+1; k=low;
  while(i<=middle&&j<=high)  //两个子序列非空
 if(A[i]<=A[j])  B[k++]=A[i++];
     else  B[k++]=A[j++];
 while (i<=middle) B[k++]=A[i++];
 while (j<=high) B[k++]=A[j++];
  for(i=low;i<=high;i++) A[i++]=B[i++];
}

 递归形式

void MergeSort (int A[],int low,int high)
{    
  int middle;
  if (low

时间复杂度

算法设计与分析基础之分治法,详解二分查找、合并以及快速排序_第4张图片

 求得T(n)=nT(1)+nlogn=n+nlogn,即合并排序算法的时间复杂性为O(nlogn)

三、快速排序

算法思想

通过一趟扫描将待排序的元素分割成独立的三个序列:第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置,因此需要再按此方法对第一个序列和第三个序列分别进行排序,整个排序过程可以递归进行,最终可使整个序列变成有序序列。

快排分治体现

1、分解  

在A[low:high]中选定一个元素作为基准元素(P),以此基准元素为标准将待排序序列划分为两个子序列并使序列A[low:P-1]中所有元素的值均小于等于A[P],序列A[P+1:high]中所有元素的值均大于等于A[P]。

2、求解子问题 对子序列A[low:P-1]和A[P+1:high],分别通过递归调用快速排序算法来进行排序。

3、合并 就地排序。

  对于基准元素P可以采取以下五种方法:

(a)取第一个元素。 (b)取最后一个元素。 (c)取位于中间位置的元素。 (d)“三者取中的规则”。 (e)取位于low和high之间的随机数,用A[P]作为基准元素。即采用随机函数产生一个位于low和high之间的随机数P(low≤P≤high),用A[P]作为基准,这相当于强迫R[low:high]中的元素是随机分布的。 

 划分方法的构造实例

图示助理解

以第一个元素作为基准元素

算法设计与分析基础之分治法,详解二分查找、合并以及快速排序_第5张图片

算法设计与分析基础之分治法,详解二分查找、合并以及快速排序_第6张图片

 具体代码实现

tips:完整代码,可复制后直接使用

#include
using namespace std;
//交换函数swap
void swap1(int& a, int& b)
{
	int temp = a; a = b; b = temp;
}
//做一个把数组分两半的函数
int sortSecond(int A[], int low, int high)
{
	int P = A[high];//基数选择右边界
	while (low < high)
	{
		while (low < high && A[low] <= P)
			low++;//左边部分小的跳过
		if (low < high){
			swap1(A[low], A[high--]);//大的扔到后面并使右边界减一
		}
		while (low=P)
			high--;//右边大的跳过
		if (low < high) {
			swap1(A[low++], A[high]);//小的扔到前面并使左边界加一
		}
	}
	return low;//此时low=high
}
void fastSort(int A[], int low, int high)
{
	if (low > high) return;//递归结束条件 low>high
	int v = sortSecond(A, low, high);
	fastSort(A, low,  v - 1);//对左区间递归排序
	fastSort(A, v + 1, high);//对右区间递归排序
}
int main()
{
	int A[9] = {4,3,1,2,4,9,5,8,6};
	int len = sizeof(A) / sizeof(A[0]);
	cout << "排序前数组为:\t" << endl;
	for (int i = 0; i < len; i++)
	{
		cout << A[i] << " ";
	}
	cout << endl;
	fastSort(A, 0, len-1);//时间复杂度 平均情况O(nlogn),最坏情况O(n^2)
	cout << "快速排序后数组为:\t" << endl;
	for (int i = 0; i < len; i++)
	{
		cout << A[i] << " ";
	}
}

我选择的是以最右边的元素作为基准元素,所以先和基准元素左边的值作比较,如果A[low]<=P,进行low++操作,反之交换数据并让让右边界减一,这是因为右半部分是和P作比较,所以没必要把判断过的数据重复判断,直到low!

 运行效果

算法设计与分析基础之分治法,详解二分查找、合并以及快速排序_第7张图片

时间复杂度

 算法设计与分析基础之分治法,详解二分查找、合并以及快速排序_第8张图片

 结语

有趣的分治法到这里就结束了,分治法是一种很重要的算法。它采取各个击破的技巧来解决一个规模较大的问题,该技巧是很多高效算法的基础,所以希望这篇博客可以被大家收藏,如果有错误或者不规范的地方一定评论出来,我每天都会管理我的博客内容,你的点赞关注评论是我前进的最大动力,加油!!!

你可能感兴趣的