再探快速排序的递进式演进，是否更易于掌握？

本文共计2005个文字，预计阅读时间需要9分钟。

一开始+爷爷有退休金，奶奶没有+奶奶非常需要强+为了不让爷爷看不清，她找了保姆的工作+结果要早起，她起不来+现在爷爷每天要早起扫大街+前提回顾+关于快排，楼主之前写过两篇

开心一刻

　　爷爷有退休金，奶奶没有

　　可奶奶很要强

　　为了不让爷爷看不起，她找了份环卫的工作

　　结果要早起，她起不来

　　现在爷爷每天要早起扫大街

前情回顾

　　关于快排，楼主之前写过两篇关于它的文章

　　排序之快速排序 → 基本版实现，排序之快速排序 → 基本版优化

　　感觉讲的有点突兀，看过之后你们的表情是这样的

　　贴心的我实在是难以忍受你们那无辜的小眼神，决定让你们的表情变成这样

两区域划分

　　问题描述：给定一个整型数组arr和一个整数target，请把小于等于target的数放在数组的左边，大于target的数放在数组的右边

　　常规实现

　　如果不做任何限制，我相信大家很容易想到如下方法

　　准备一个新数组，然后遍历arr，arr素逐个与target进行比较

　　小于等于target的元素从左往右放入到新数组中，大于target的元素从右往左放入到新数组中

　　当arr遍历完，新数组中的元素顺序即是：小于等于target的数在左边，大于target的数在右边

　　我们来看代码实现

　　假设arr是[9,8,3,2,6,4,5,0,1,1,1]，target是 7，那么得到的结果是[3,2,6,4,5,0,1,1,1,8,9]

　　细心的小伙伴会大声道：你这不对，3 怎么在 2 的前面，6 的位置也不对，...

　　现在是区域划分，不是排序、不是排序、不是排序！

　　我们换个方式来看

　　现在清楚了吧

　　我们从两个维度来看看这个算法的优劣，时间复杂度O(N)，额外空间复杂度O(N)

　　时间复杂度已经没法优化，额外空间复杂度能不能优化了？

　　优化实现

　　常规实现中，用了一个新的数组，那有没有什么办法拿掉这个新数组后，仍然可以完成区域的划分了？

　　我们记录边界索引lte，lte左边是小于等于区域，lte至遍历索引 i 之间是大于区域，具体实现步骤如下

　　分两种情况进行处理

　　　　1、如果arr[i] <= target，则arr[i]和lte的前一个元素进行交换，lte右移，i++

　　　　2、如果arr[i] > target，lte不动，i++

　　我们看个具体案例就懂了

　　相当于小于等于区推着大于区往后走

　　再来看具体代码实现

　　此时，时间复杂度O(N)，只用到了一个额外变量lte，所以额外空间复杂度O(1)

荷兰国旗（三区域划分）

　　我们把问题进行一个升级：给定一个整型数组arr，和一个数 target，请把小于target的数放在数组的左边，等于target的数放在数组的中间，大于target的数放在数组的右边

　　荷兰国旗是三种颜色

　　正好对应问题描述中的三个区域，所以也称这个问题为荷兰国旗问题

　　常规实现

　　可以在两区域划分的常规实现的基础上进行改造；我们直接看代码

　　很明显，时间复杂度O(N)，额外空间复杂度O(N)

　　时间复杂度已经没法优化了，我们需要优化额外空间复杂度

　　优化实现

　　如果要求额外空间复杂度 O(1)，时间复杂度 O(N)

　　类比两区域划分的优化实现，我们分两个边界索引，左边界索引lt往左是小于区，右边界索引gt往右是大于区，lt至遍历索引 i 之间是等于区域，i 至gt之间是待定（未比较）区域

　　分三种情况进行处理：

　　　　1、arr[i] < target，arr[i]和lt后一个元素进行交换，lt右移，i++

　　　　2、arr[i] == target，i++

　　　　3、arr[i] > target，arr[i]和gt前一个元素进行交换，gt左移，i 不动

　　我们来看个具体案例就理解了

　　是不是有点感觉了？

　　我们再来看看代码的实现

　　时间复杂度O(N)，仅用了有限几个变量，额外空间复杂度O(1)

快速排序

　　配角已经悉数登场，接下来有请主角登场

　　1.0 版本

　　基于两区域划分，我们来实现快速排序

　　1、我们取最后一个元素作为target，将最后一个元素之前（不包括最后一个元素）所有元素进行一次两区域划分，然后将大于区的第一个元素与target进行交换

　　2、此时target所在的位置是lte + 1，然后对left ~ lte和lte+2 ~ right这两个区域分别做两区域划分

　　3、重复步骤1、2，最终实现排序

　　直接看代码

　　2.0 版本

　　类似荷兰国旗问题对两区域划分的优化，一次处理一批等于target的元素

　　处理步骤与1.0 版本类似，如下

　　1、取最后一个元素作为target，将最后一个元素之前的元素按荷兰国旗问题处理，然后将大于区域的第一个元素与target进行交换

　　2、此时，lt+1 ~ gt范围的元素都等于target，不需要再处理；只需要对left ~ lt和gt+1~ right这两个区域分别做荷兰国旗问题处理

　　3、重复步骤1、2，最终实现排序

　　代码实现如下：

　　3.0 版本

　　不管是1.0 版本还是2.0 版本，时间复杂度都是 O(N²)，比如对[1,2,3,...,N-1,N]进行排序

　　时间复杂度就是：O(N-1 + N-2 + ... + 2 + 1)，常数项可以忽略，也就是 O(N²)

　　因为我们取target的时候，固定取的最右边元素，所以我们需要随机取target

　　我们可以从left ~ right中随机取一个元素作为target，然后以此target对arr[left...right]做荷兰国旗问题处理

　　代码实现如下：

　　partition 版本

　　其实就是3.0 版本的另外一种叫法

　　实现基本一致，如下

总结 　　演进过程

　　从两区域划分->荷兰国旗问题->快速排序

　　快排 1.0 -> 快排 2.0 -> 快排 3.0

　　递进式实现，便于大家理解快速排序

　　注意点

　　实现的过程中，一些边界值需要注意

　　边画图，边梳理，结合实际案例进行分析实现