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

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

目录

二分查找

问题描述

算法思想

构造实例

实现方法

1、两种非递归

2、递归算法

时间复杂度

二、合并排序

算法思想

合并方法

算法描述

非递归形式

递归形式

时间复杂度

三、快速排序

算法思想

快排分治体现

划分方法的构造实例

图示助理解

具体代码实现

运行效果

时间复杂度

 结语

二分查找 问题描述

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

算法思想

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

构造实例

创建数组并随机赋值，定义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  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;
}

 时间复杂度

二、合并排序 算法思想

合并排序是采用分治策略实现对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