快速排序的挖坑法与prev、cur法，我们在上一篇博客的第6个排序中讲的非常详细，http://10740184.blog.51cto.com/10730184/1774508【数据结构】常用排序算法（包括：选择排序，堆排序，冒泡排序，选择排序，快速排序，归并排序）
有兴趣的话，相信聪明的你，一看就会秒懂快速排序的思想。
下面，我们将快速排序优化：
1、三数取中来优化快速排序
优化原因：
快速排序的擦差不多每次将序列一分为二，时间复杂度是O(n*lgn).
我们思考，快速排序的时间复杂度是O(n*lgn)，在序列乱序时，它的效率很高。但是，当序列有序或者接近有序时，效率就没有那么高了。
如果一个序列是这样的：
｛10，5，1，4，5，9，6，1｝
我们针对上述序列，如果要排成升序的话，我们要找一个数满足挖坑法里面的挪数据条件，或者说prev、cur法中的交换数据条件时，可能一直将序列从头遍历，找到结束或者快要结束才找到或者还没有找到，这时候相当于效率就变成了o(n^2)了。
优化方法：
因此，我们想到了三数取中的思想。即序列的三个位置最左边left,最右边right,中间mid，三个数取出中间大小的数，用这个数做key.
三数取中的代码如下：
2.非递归的实现
优化原因：
当一个序列较小时，每次将序列再成两半，递归处理两半的序列。
但是，当要给20万、30万这样的序列排序时，每次递归的话，无疑每次调用函数建立栈帧会很很大的系统开销，甚至会耗尽系统的空间。
优化方法：用栈stack模拟实现栈帧，每次压栈出栈---》即递归写法。
递归代码如下：
非递归代码如下（推荐）：