上次我们讲完了选择排序，堆排序和冒泡排序后，这次我们来讲解一下快速排序。
快速排序又分为Hoare版本，挖坑法，前后指针法，接下来，我们来一一讲解。
首先先基本了解快速排序：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，
其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
简单理解就是：
现在给出它的Hoare版本的快速排序动图：
Hoare排序思路:
我们观察动图可以知道，选取了基准值后（一般放到最左边的位置），先让右边先出发。
右边的任务是寻找比基准值小的数，找到后就停。
轮到左边，左边的任务是寻找比基准值大的数，找到就停。
若此时，left和right还为相遇，就交换left和right的数。
再继续按照上面的寻找。直到相遇（left==right），就停止寻找，最后交换key的值和相遇的位置值。
这样就可以分成两部分：一部分比基准值小，一部分比基准值大。
接着继续按照这种思路，把剩下的同样完成。
错误点分析 代码：
void QuickSort(int* a, int left,int right)
{int keyi = left;left++；while (left<right){while (a[right] > a[keyi])right--;while (a[left] < a[keyi])left++;;Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);}错误1.
有人按照上面的思路，会写出上面的代码。但是这是有问题的：
如果是上面的这种情况，当出现多个与基准值一样的数时，我们没有让它等于时进入循环 发现它会出现死循环，所以要加上=
while (a[right] >= a[keyi])right--;while (a[left] <= a[keyi])left++;;
错误2 ：
上面情况下，你会发现会发生错误了。所以还要加上 这样的条件：
while (left<right && a[right] >= a[keyi])right--;while (left<right && a[left] <= a[keyi])left++;;
3.left--错误
int keyi = left;left++；你想想，代码的后面是不是要交换的，可你现在left的位置是一直变化的，是不是就找不到原来的位置了啊？
所以呢？我们还要进行记录原来的位置下来：
int keyi = left;int begin = left, end = right;最后，正确的代码应该是：
void QuickSort(int* a, int left,int right)
{int keyi = left;int begin = left, end = right;while (left<right){while (left<right &&a[right] >= a[keyi])right--;while (left<right &&a[left] <= a[keyi])left++;;Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);}接下来的部分，又两种的方法可以完成：一直是递归法，一种是非递归法。两种都要掌握。递归变非递归是每个程序员必备的技能，所以都需要会。
这里我们先来
快速排序的递归法：
大概递归的过程就是这样了。就是每次都分成两部分。
观察到，什么时候是结束递归？就是当left>=right时就返回来了。
它递归的范围是什么呢？第一趟完成的时候，我们可以很清楚看到，分成两部分的范围应该是：
[begin,keyi-1]keyi,[key+1,end]
有了上面的了解后，我们就可以写出来递归的代码了：直接对照范围写下来就可以了。
代码：
void QuickSort(int* a, int left,int right)
{if (left>=right)return;int keyi = left;int begin = left, end = right;while (left<right){while (left<right &&a[right] >= a[keyi])right--;while (left<right &&a[left] <= a[keyi])left++;;Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;//[0,keyi-1]keyi,[key+1,end]QuickSort(a, begin, keyi-1);QuickSort(a,keyi+1,end);}其实，看下递归图后，不知道大家有没有一种熟悉感，就是它特别像二叉树？
而我们的二叉树中算过2^n-1的节点
所以若有N个数，每次它会减少一个数，所以排序的的平均时间复杂度大概是O(N*logN)；
但是它的最坏时为O(N^2);
完全逆序时，如上图，次数有等差数列直到，n^2/2 大概就是n^2了
证明：左边做key，右边先走，为啥相遇位置就是基准值的位置？
相遇：
1.R找到小的了，L没有找到大的，那么L会相遇R
2.R找小没有找到，直接遇到L，那么它就是比key基准值小的位置或者直接到到key基准值。
3.按照此类似的，当我们选取右边为基准值时，让左边先，也是同样的道理。
可是呢，当我们仅仅是取左边的数或者是右边的数，这偶然性太大了，万一它是最小的数/最大的数，这是不是效率就非常的低了。为了解决这种误差，大佬们想出了几种解决方法：
三数取中，取随机数，取完了之后再进行交换。这样就大大提高了它们的效率了。
三数取中：看名字知道，就是取三个数，比较大小，选取中间大的数做基准值。
三数取中：
//三数取中
int GetMidNum(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if(a[left]>a[right]){return left;}else{return right;}}else{if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}取随机数：
//随机数int randi = left+rand() % (right - left);Swap(&a[randi], &a[left]);随便都可以用一个。
挖坑法：
动图：
代码：
void QuickSort2(int* a,int left,int right)
{if (left >= right)return;//三数取中//int midi = GetMidNum(a, left, right);//if (midi != left)//{// Swap(&a[midi], &a[left]);//}int begin = left, end = right;int key = a[left];int hole = left;while (left < right){while (left<right &&a[right] >= key)right--;Swap(&a[right], &a[hole]);hole = right;while (left<right &&a[left] <= key)left++;Swap(&a[left], &a[hole]);hole = left;}a[hole] = key;//范围//[begin,empty-1][empty+1,end]QuickSort2(a, begin, hole - 1);QuickSort2(a, hole +1,end);}
前后指针法：
动图：
步骤：
1.如果cur的值小于基准值，则prev++，且交换prev和cur的位置，cur++；
2.如果cur的值大于基准值，cur++；
3.看动图，我们知道当cur+1<n时，不进入循环，不能cur<n.
此时交换key的值和prerv的值
说明：
1.prev要么紧跟的cur（prev的next是cur）
2.prev跟cur中间间隔着比key基准值大的一段数的区间。
看到上面的红色部分，我们可以看出，prev和cur之间的区间是不是轮流翻转的规律的。
代码：
//指针法
void QuickSort3(int* a, int left, int right)
{if (left >= right)return;int midi = GetMidNum(a, left, right);if (midi != left){Swap(&a[left], &a[midi]);}int keyi = left;int prev = left, cur = left + 1;while (cur < right+1){if (a[cur] < a[keyi] && prev++ !=cur)Swap(&a[cur], &a[prev]);cur++;}Swap(&a[keyi], &a[prev]);//换了位置，keyi也要变，具体的选择排序那里有讲过原因keyi = prev;//QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi + 1, right);}最后，到了本次的鸡汤部分：
我们都懂得努力，但不知道如何开始，既然还在边缘徘徊，何不如先扎根一回探其究竟，与其焦急等待，不如快速做出决定。当你再次回头的时候，也许你会看到同在起点的他们还在原地，而你已经超越。
