看完这个，你觉得你真的懂快速排序吗？( 二 ) _排序

版本一使用双指针交替从左(右)两边分别开始寻找大于基准值(小于基准值) ，然后与基准值交换，直到最后左右指针相遇。
版本二使用双指针向中间集合，左指针遇到大于基准值时则停止，等待右指针，右指针遇到小于基准值时则停止，与左指针指向的元素交换，最后基准值放到合适位置。

过程说起来比较抽象，稳住别慌！灵魂画手大白会画图来演示这两个过程。

文章插图

快速排序的递归演示

版本一递归代码的排序过程示意图：

以第一次递归循环为例:

文章插图

步骤1: 选择第一个元素为基准值pivot=a[left]=5,right指针指向尾部元素，此时先由right自右向左扫描直至遇到<5的元素，恰好right起步元素4<5 ，因此需要将4与5互换位置；
步骤2: 4与5互换位置之后，轮到left指针从左向右扫描，注意一下left的起步指针指向了由步骤1交换而来的4 ，新元素4不满足停止条件，因此left由绿色虚箭头4位置游走到元素9的位置，此时left找到9>5 ，因此将此时left和right指向的元素互换，也就是元素5和元素9互换位置；
步骤3: 互换之后right指针继续向左扫描，从蓝色虚箭头9位置游走到3的位置，此时right发现3<5 ，因此将此时left和right指向的元素互换，也就是元素3和元素5互换位置；
步骤4: 互换之后left指针继续向右扫描，从绿色虚箭头3位置游走到6的位置，此时left发现6>5 ，因此将此时left和right指向的元素互换，也就是元素6和元素5互换位置；
步骤5: 互换之后right指针继续向左扫描，从蓝色虚箭头6位置一直游走到与left指针相遇，此时二者均停留在了pivot=5的新位置上，且左右两边分成了两个相对于pivot值的子序列；
循环结束：至此出现了以5为基准值的左右子序列，接下来就是对两个子序列实施同样的递归步骤。
以第二次和第三次左子序列递归循环为例:

文章插图

步骤1-1：选择第一个元素为基准值pivot=a[left]=4 ， right指针指向尾部元素，此时先由right指针向左扫描，恰好起步元素3<4 ，因此将3和4互换；
步骤1-2：互换之后left指针从元素3开始向右扫描，一直游走到与right指针相遇，此时本次循环停止，特别注意这种情况下可以看到基准值4只有左子序列，无右子序列，这种情况是一种退化，就像冒泡排序每次循环都将基准值放置到最后，因此效率将退化为冒泡的O(n^2);
步骤1-3：选择第一个元素为基准值pivot=a[left]=3 ， right指针指向尾部元素，此时先由right指针向左扫描，恰好起步元素1<3 ，因此将1和3互换；
步骤1-4：互换之后left指针从1开始向右扫描直到与right指针相遇，此时注意到pivot=3无右子序列且左子序列len=1 ，达到了递归循环的终止条件，此时可以认为由第一次循环产生的左子序列已经全部有序。
循环结束：至此左子序列已经排序完成，接下来对右子序列实施同样的递归步骤，就不再演示了，聪明的你一定get到了。
特别注意:
以上过程中left和right指针在某个元素相遇，这种情况在代码中是不会出现的，因为外层限制了i!=j ，图中之所以放到一起是为了直观表达终止条件。

版本二C++版本动画演示：

文章插图

分析一下:
个人觉得这个版本虽然同样使用D&C思想但是更加简洁，从动画可以看到选择pivot=a[end] ，然后左右指针分别从index=0和index=end-1向中间靠拢。
过程中扫描目标值并左右交换，再继续向中间靠拢，直到相遇，此时再根据a[left]和a[right]以及pivot的值来进行合理置换，最终实现基于pivot的左右子序列形式。