算法思想

规模为N的原问题的解无法直接求出，进行问题规模的缩减，划分子问题（这里子问题相互独立而且和原问题的解得性质是相同的，知识问题的规模缩小了）。如果子问题的规模仍然不够小，在进行子问题的划分，如此递归的进行下去，知道子问题规模足够小，很容易求出其解为止，最后将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

其实就是通过递归化繁为简，又简逐层回溯到原问题，常见的例子有快速排序和归并排序

快排分割找TopK问题

问题描述：

在一段序列中找第K大的元素，这里利用的是快速排序的思想，也可以用大小根堆解决此问题

算法思想：

代码描述：

int  QuickSortFindTop(vector<int>& arr, int left, int right,int key)
{
	int s_left = left;
	int s_right = right;
	int val = arr[left];
	while (s_left < s_right)
	{
		while (s_left < s_right && arr[s_right] >= val)
			s_right--;
		if (s_left < s_right)
		{
			arr[s_left] = arr[s_right];
			s_left++;
		}
		while (s_left < s_right && arr[s_left] <= val)
			s_left++;
		if (s_left < s_right)
		{
			arr[s_right] = arr[s_left];
			s_right--;
		}
	}
	arr[s_left] = val;
	if (s_left < arr.size()-key)
	{
		QuickSortFindTop(arr, s_left + 1, right,key);
	}
	else if (s_left > arr.size() - key)
	{
		QuickSortFindTop(arr, left, s_left - 1,key);
	}
	else
	{
		return s_left;
	}
}

归并排序

归并排序是最接近分治算法思想的，将序列递归到最小序列（只有一个元素），然后向上回溯，在回溯的过程中开辟空间进行排序.

代码实现：
 

void merge(vector<int>& vec, int left, int right, int mid)
{
	vector<int>tmp;
	tmp.reserve(right - left + 1);
	int low = left;
	int high = right;
	int mmid = mid + 1;
	//开始合并
	while (low<=mid&&mmid<=right)
	{
		if (vec[low] <= vec[mmid])
		{
			tmp.push_back(vec[low]);
			low++;
		}
		if (vec[low] > vec[mmid])
		{
			tmp.push_back(vec[mmid]);
			mmid++;
		}
	}
	//判断容器是否有剩余
	while (low <= mid)
		tmp.push_back(vec[low++]);
	while (mmid <= right)
		tmp.push_back(vec[mmid++]);
	//此时，容器归并完成,开始放到原容器中
	int nec = 0;
	while (left <= right)
	{
		vec[left++] = tmp[nec++];
	}

}
void MergeSort(vector<int>& vec, int left, int right)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	MergeSort(vec, left, mid);
	MergeSort(vec,mid+1, right);
	//分完了,开始回溯
	merge(vec, left, right, mid);
}