活动地址：CSDN21天学习挑战赛

前言

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

快速排序的正解

算法思想

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

快排分治体现

1. 分解

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

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

3. 合并 就地排序。

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

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

具体代码实现

#include<iostream>
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<high && A[high]>=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!<high，返回low的值，而且不难想到此时low=high。

有趣的分治法到这里就结束了，分治法是一种很重要的算法。它采取各个击破的技巧来解决一个规模较大的问题，该技巧是很多高效算法的基础，所以希望这篇博客可以被大家收藏，如果有错误或者不规范的地方一定评论出来!