常见的排序算法有以上八种，所以预估会分成几期来讲，感兴趣的朋友们不妨点个收藏专栏。 ღ( ´･ᴗ･` )比心

OJ链接

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

将区间按照基准值划分为左右两半部分的常见方式: Hoare法、挖坑法、前后指针法。

快排又可以通过递归和非递归的方式进行实现。

1. 当选择左边的值做key时，右边先走。
2. 当选择右边的值做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、挖坑法或者前后指针法进行单趟排序，再通过递归分别处理左区间和右区间。