核心思想：选择一个合适的数作为“主元”，然后将待排数据分为大于主元的和小于主元的，接下来“分而治之”，分别排好左边和右边，最后直接合在一起。
选主元
- 取头、中、尾的中位数
- 例如，8、12、3的中位数就是8
- 下面我们需要将这个数组划分为左右两个子集，左边都比
Pivot小，右边都比Pivot大。由于在上面的比较过程中我们已经确定了Left一定比Pivot小，Right一定比Pivot大，所以这两个不用传入，我们将Pivot放在Right-1的位置传入；
子集划分
将划分子集的过程想象成一棵树
- 快排之所以”快“的原因，是主元每次排好后位置就固定了，不会频繁移动；
- 新建两个指针：
i和j，如果i碰到比Pivot大的就停下来移动j，j碰到比Pivot小的就停下来，此时i指向的元素比Pivot大、j指向的元素比Pivot小，交换这两个元素，然后接着移动。
- 停止条件：当需要交换的时候，判断一下
i是否在j的右边，如果在说明需要停止了，否则就交换；
8 | 1 | 4 | 9 | 0 | 3 | 5 | 2 | 7 | 6 |
i | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | j | ㅤ |
8 | 1 | 4 | 9 | 0 | 3 | 5 | 2 | 7 | 6 |
i | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | j | ㅤ | ㅤ |
2 | 1 | 4 | 9 | 0 | 3 | 5 | 8 | 7 | 6 |
i | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | j | ㅤ | ㅤ |
2 | 1 | 4 | 9 | 0 | 3 | 5 | 8 | 7 | 6 |
ㅤ | i | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | j | ㅤ | ㅤ |
2 | 1 | 4 | 9 | 0 | 3 | 5 | 8 | 7 | 6 |
ㅤ | ㅤ | i | ㅤ | ㅤ | ㅤ | ㅤ | j | ㅤ | ㅤ |
2 | 1 | 4 | 9 | 0 | 3 | 5 | 8 | 7 | 6 |
ㅤ | ㅤ | ㅤ | i | ㅤ | ㅤ | ㅤ | j | ㅤ | ㅤ |
2 | 1 | 4 | 9 | 0 | 3 | 5 | 8 | 7 | 6 |
ㅤ | ㅤ | ㅤ | i | ㅤ | ㅤ | j | ㅤ | ㅤ | ㅤ |
2 | 1 | 4 | 5 | 0 | 3 | 9 | 8 | 7 | 6 |
ㅤ | ㅤ | ㅤ | i | ㅤ | ㅤ | j | ㅤ | ㅤ | ㅤ |
2 | 1 | 4 | 5 | 0 | 3 | 9 | 8 | 7 | 6 |
ㅤ | ㅤ | ㅤ | ㅤ | i | ㅤ | j | ㅤ | ㅤ | ㅤ |
2 | 1 | 4 | 5 | 0 | 3 | 9 | 8 | 7 | 6 |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | i | j | ㅤ | ㅤ | ㅤ |
2 | 1 | 4 | 5 | 0 | 3 | 9 | 8 | 7 | 6 |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | j i | ㅤ | ㅤ | ㅤ |
2 | 1 | 4 | 5 | 0 | 3 | 9 | 8 | 7 | 6 |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | j | i | ㅤ | ㅤ | ㅤ |
2 | 1 | 4 | 5 | 0 | 3 | 6 | 8 | 7 | 9 |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | j | i | ㅤ | ㅤ | ㅤ |
如果有元素正好等于
Pivot 怎么办？- 停下来交换
- 不理它，继续移动指针
- 对于1，每次都交换，好处是每次基本上都能将数组等分，最后时间复杂度是；对于2，由于一直在移动最左边的指针，最后会将子集划分成左边一大堆数和右边只有一个数，相当于树往一遍歪了，最后时间复杂度就会来到。所以我们一般选择方法1。
- 快速排序的问题：使用递归，对小规模的数据可能还不如插入排序快；
- 解决方法：
- 当递归的数据规模充分小，则停止递归，直接调用简单排序（如插入排序等）
- 在程序中定义一个
Cutoff的阈值