目录
1.挖坑法
2.左右指针法
3.前后指针法
4.快排优化 -- 三数取中法
快速排序毋庸置疑是最快的排序！？要不对不起它这个名字，哈哈。
这里都以升序为例子。
一般都是取第一个做pivot，key=arr[pivot]，思想就是使key左边都比key小，右边都比key大。
[left,pivot-1] pivot [pivot+1,right]
然后再递归分治arr数组中的左边和右边直到只有一个数字。
单趟排序如下图：
整体代码如下，注释详细：
注意循环里面的循环条件不要忘记 bagin < end ，不然可能会越界。
同样 while里面的找小条件要arr[end] >= key ，这里一定要>=否则可能会死循环。
找大同理。
其思想完全和第一种一样，就是这种找比key大或小是用左右两个指针完成的。
整体代码如下，注释详细：
这种实现和上面两种略有不同。
还是取第一个值的下标作keyi，利用前面两个指针 prev cur
cur找小，每次遇到比keyi小的值就停下来，prev++，交换prev和cur位置的值
如下图：
整体代码如下，注释详细：
众所周知，快速排序的时间复杂度为O(N*logN)
什么时候最坏呢？
当然是每次取的key恰好是最大值或者最小值，即数组已经有序，这时的时间复杂度就是O(N^2)
大致如下图：
为了避免这种情况可以，让key取尽量中间值即三数取中法。
整体代码如下，注释详细：
下面是对挖坑法优化，其他方法优化一样，调用一下GetMidIndex函数就行了。