目录

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函数就行了。