一步，一步
基础快排：
将区间分为两部分，小于等于 和 大于
双路快排：
将区间分为两部分，小于等于 和 大于等于，重复元素等概率的分配到这两部分中
三路快排：
三路快排又多加了一个指针，用于将区间分为三部分
二路快排是将与基准值相等的元素，等概率的分配到左右两部分
三路快排则是将与基准值相等的元素，集中在区间的中间部分(紧接小于基准值区间的右边)
arr[left] 基准值
arr[left + 1, lt] 小于基准值的区间
arr[lt+1, i - 1] 等于基准值的区间
arr[i, gt - 1] 暂未被遍历的区间
arr[gt, right] 大于基准值的区间
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例：
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
提示：
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
先来分析一下基础快排的问题，再来实现双指针快排
有两个哨兵
lt和i， 它们都向右移动
lt记录当前序列 小于基准值区间内的最后一位元素
i遍历整个[left, right]区间：
- 发现小于等于 基准值的元素，则与
lt位置的元素进行交换- 发现大于 基准值的元素，跳过不做任何操作
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
说明：
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
基本思路：找一个基准数(pivot)，遍历[left, right]区间，比基准数小的数放在它的左边，比基准数大的放在它右边。此时这个基准数所在位置就已经确定了（每次遍历都会确定当前基准数的位置）。随后递归地去排它左边部分和右边部分，直到数组有序。
通过基准数将当前数组一分为二的过程称为：切分(partition)
归并排序的优化
**基本思路：**借助额外空间，合并两个有序数组，得到更长的有序数组
**算法思想：**分而治之（分治思想）。「分而治之」