前言
之前介绍的插入排序与冒泡排序算法存在一个很明显的问题，就是基于比较和交换的排序策略，从根本上无法对平均时间复杂度进行优化，没有改进的余地和空间。
但是如果我们摒弃插入排序与冒泡排序的思想，另辟蹊径是否能够提升排序效果呢？
答案是肯定的。下面将介绍基于分治策略的两种排序算法，分别是快速排序算法和归并排序算法，并对其进行时间复杂度分析和改进。
一、分治策略首先，我们先了解一下什么是分治策略。
分治策略：如果一个规模为n的问题，若该问题可以很容易地解决（n较小）时，则直接解决；否则将其分解为k个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解进行合并得到原问题的解。如果子问题不独立有公共子问题，那么我们则使用动态规划的思想求解该问题。
分治策略分成三个步骤：
分解：将原问题分解为若干个规模较小的子问题，相互独立，与原问题形式形同的子问题。解决：若子问题规模较小而容易被解决则直接解决，否则递归地解决各个子问题。合并：将各个子问题的解合并为原问题的解。分治法步骤
分治法时间复杂度如下
当采用分治法时，
时，时间复杂度等于”分解+解决+组合“三部分的和。分治与递归是一对“孪生兄弟”，经常搭配在一起使用，解决很多问题。
采用分治策略主要有两种算法：
快速排序：hard division, easy combination.归并排序：easy division, hard combination. 二、快速排序过程快速排序--图片来源：https://blog.csdn.net/engineerhe/article/details/104131452
上图是一个快速排序算法的动态演示，略显抽象，我们可以通过另一幅图片来看。
快排过程分解--图片来源：https://blog.csdn.net/engineerhe/article/details/104131452
上图的过程是快速排序的基本过程，快排会先选择一个元素作为枢轴，小的放在他的左边，大的放在他的右边，从而经过n-1次比较，将原问题划分为两个相同的子问题。进而再对两个子问题进行相同的求解过程。
示例代码如下：
public 三、快排时间复杂度分析有了代码实现，下面我们要进行快排的时间复杂度分析。
还是按照我们的脉络，先分析最坏情况，再分析最好情况。
最坏情况时间复杂度最坏情况是选取的枢轴是最小的元素，导致划分后的问题规模是0和n-1，然后接下来枢轴仍然是最小值。给出一个例子，”1, 2, 3, 4, 5, 6, 7, 8, 9, 10“，假设每次选取第一个元素作为枢轴，那么这个序列就对应着最坏情况。
我们递推求得该问题的最坏情况时间复杂度为
。2. 平均时间复杂度
h设所有的可能的输入序列都是等可能性出现的。
我们将所有可能的情况加和起来，进一步可以得到
可以通过将上式展开得到下式。
进而我们有两种方法来得到A(n)，一种是估算法，一种是直接推理法。
①估算法
估算快排时间复杂度为
根据定理3.7的第二个条件，进而我们可以得到
②直接推理计算
这里直接给出过程，大家可以按照过程推导一遍，此处并不做特殊要求。
四、快速排序算法的改进
改进措施：
递归：因为递归调用过程是要消耗计算资源的，因此可以改为非递归小排序问题：小排序可以使用其他排序算法枢轴的选取--随机打乱、随机选择等等方法但是随机打乱、随机选择还是无法避免最坏情况的出现。如果快排策略不改变，无论如何选用枢轴，都存在最坏情况
。