• 版本二 C++实现

#include
using namespace std;

template 
void quick_sort_recursive(T arr[], int start, int end) {
    if (start >= end)
        return;
    T mid = arr[end];
    int left = start, right = end - 1;
    //整个范围内搜寻比枢纽值小或大的元素，然后左侧元素与右侧元素交换
    while (left < right) {
            //试图在左侧找到一个比枢纽元更大的元素
        while (arr[left] < mid && left < right)
            left++;
                //试图在右侧找到一个比枢纽元更小的元素
        while (arr[right] >= mid && left < right)
            right--;
                //交换元素
        std::swap(arr[left], arr[right]);
    }
        //这一步很关键
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;
    quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}

//模板化
template  
void quick_sort(T arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

int main()
{
    int a[9]={5,1,9,6,7,11,3,8,4};
    int len = sizeof(a)/sizeof(int);
    quick_sort(a,len-1);
    for(int i=0;i

两个版本均可正确运行，但代码有一点差异:

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

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

快速排序的递归演示

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

以第一次递归循环为例:

步骤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的左右子序列形式。

脑补场景:

上述过程让我觉得很像统帅命令左右两路军队从两翼会和，并且在会和过程中消灭敌人有生力量(认为是交换元素)，直到两路大军会师。

此时再将统帅王座摆到正确的位置，此过程中没有统帅王座的反复变换，只有最终会师的位置，以王座位中心形成了左翼子序列和右翼子序列。

再重复相同的过程，直至完成大一统。

脑补不过瘾 于是凑图一张:

快速排序的多种版本

吃瓜时间：

印象中2017年初换工作的时候去CBD一家公司面试手写快排，我就使用C++模板化的版本二实现的，但是面试官质疑说这不是快排，争辩之下让我们彼此都觉得对方很Low，于是很快就把我送出门SayGoodBye了^_^。

我想表达的意思是，虽然快排的递归版本是基于D&C实现的，但是由于pivot值的选择不同、交换方式不同等诸多因素，造成了多种版本的递归代码。

并且内层while循环里面判断>=还是>(即是否等于的问题)，外层循环判断本序列循环终止条件等写法都会不同，因此在写快排时切忌死记硬背，要不然边界条件判断不清楚很容易就死循环了。

看下上述我贴的两个版本的代码核心部分：

//版本一写法
while(i!=j){
    while(i=temp){
        j--;
    }
    exchange(&a[i],&a[j]); 
    while(i= mid && left < right)
        right--;
    std::swap(arr[left], arr[right]);
}

覆盖or交换:

代码中首先将pivot的值引入局部变量保存下来，这样就认为A[L]这个位置是个坑，可以被其他元素覆盖，最终再将pivot的值填到最后的坑里。

这种做法也没有问题，因为你只要画图就可以看到，每次坑的位置是有相同元素的位置，也就是被备份了的元素。

个人感觉 与其叫坑不如叫备份，但是如果你代码使用的是基于指针或者引用的swap，那么就没有坑的概念了。

这就是覆盖和交换的区别，本文的例子都是swap实现的，因此没有坑位被最后覆盖一次的过程。

快速排序的迭代实现

所谓迭代实现就是非递归实现一般使用循环来实现，我们都知道递归的实现主要是借助系统内的栈来实现的。

如果调用层级过深需要保存的临时结果和关系会非常多，进而造成StackOverflow栈溢出。

Stack一般是系统分配空间有限内存连续速度很快，每个系统架构默认的栈大小不一样，笔者在x86-CentOS7.x版本使用ulimit -s查看是8192Byte。

避免栈溢出的一种办法是使用循环，以下为笔者验证的使用STL的stack来实现的循环版本，代码如下：

#include 
#include 
using namespace std;

template
void qsort(T lst[], int length) {
    std::stack > mystack;
    //将数组的首尾下标存储 相当于第一轮循环
    mystack.push(make_pair(0, length - 1));

    while (!mystack.empty()) {
        //使用栈顶元素而后弹出
        std::pair top = mystack.top();
        mystack.pop();

        //获取当前需要处理的子序列的左右下标
        int i = top.first;
        int j = top.second;

        //选取基准值
        T pivot = lst[i];

        //使用覆盖填坑法 而不是交换哦
        while (i < j) {
            while (i < j and lst[j] >= pivot) j--;
            lst[i] = lst[j];
            while (i < j and lst[i] <= pivot) i++;
            lst[j] = lst[i];
        }
        //注意这个基准值回填过程
        lst[i] = pivot;

        //向下一个子序列进发
        if (i > top.first) mystack.push(make_pair(top.first, i - 1));
        if (j < top.second) mystack.push(make_pair(j + 1, top.second));
    }
}

int main()
{
    int a[9]={5,1,9,6,7,11,3,8,4};
    int len = sizeof(a)/sizeof(int);
    qsort(a,len);
    for(int i=0;i