常见的排序算法有以上八种，所以预估会分成几期来讲，感兴趣的朋友们不妨点个收藏专栏。 ღ( ´･ᴗ･` )比心
OJ链接
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式: Hoare法、挖坑法、前后指针法。
快排又可以通过递归和非递归的方式进行实现。
- 当选择左边的值做key时，右边先走。
- 当选择右边的值做key时，左边先走。
本文默认排升序，如图，选择左边值是key。右边先走，找比key小的值停下来，然后左边再走，找到比key大的停下来。交换左右两边的值，知道左右两者相遇。相遇点的值和key值交换。
Hoare版本变形。
1、同样的，选择左边的值做key，右边先走；
2、选择右边的值做key，左边先走。
右边找小，把比key小的值放进坑里，右边形成新的坑；左边找大扔到坑里，左边形成新的坑。
key选择不同，prev和cur的位置也不同。
当左边的值做key时，cur找比key小的值，找到比key小的值就停下来，++prev，交换prev和cur的值。
对于理想的快排，每次基准值如下：
时间复杂度是 O(N*logN)
但是当数组是有序时：
快排退化成冒泡排序。
解决方法：
1、随机取key值
2、三数取中。
但是三数取中 遇到数组元素相同的情况又会失效。
三数取中：
快速排序的递归实现类似二叉树的前序遍历过程。
先使用Hoare、挖坑法或者前后指针法进行单趟排序，再通过递归分别处理左区间和右区间。