一、基本思路
传统快排只是把数组分成两段进行排序，但是这样遇到重复数字多的数组就会超时，所以引入数组分三块：
流程：
1、初始化：l = -1, r = nums.size();
2、先随机数选出 key 作为基准元素。srand(time(NULL)); int key = nums[rand() % (right - left + 1) + left]
3、以 key 作为基准元素，符合 f 性质的放左边，符合 g 性质的放右边，等于 key 放中间。
4、放左边：swap(nums[l + 1], nums[i]); l++; i++; 提炼：swap(nums[++l], nums[i++]);
放右边：swap(nums[r - 1], nums[i]); r--; 提炼：swap(nums[--right], nums[i]);
放中间：i++;
5、当 i 与 r 相遇时就是 key 位置排好了。左右两边符合 f, g 性质。
6、如果还要进一步对两边排序就继续递归，范围 [left, l] 和 [r, right]
二、例题
1、颜色分类
. - 力扣（LeetCode）
目的：0，1，2有序排序
思路：选 key 等于1，左边是0，右边是2，根据性质进行数组分三段排序。
2、排序数组
. - 力扣（LeetCode）
目的：排序
思路：随机数选出 key，数组分三段排序 [left, right] 区域，递归 [left, l] 和 [r, right]
3、topK选出第K大元素
. - 力扣（LeetCode）
目的：让第K大元素落在key区域，最后直接返回key
思路：参考上图，
当 k <= c，范围缩小：[r, right] 区域找第k大元素
当 k <= b + c，刚好落在key区域，返回答案key
当 k <= a + b + c，范围缩小，[left, l] 区域找第 k - a - b 大元素
4、topK选出前K小元素
. - 力扣（LeetCode）
目的：由于返回答案不要求顺序，所以只要 a + b 的个数大于 k 就代表答案可以返回了
思路：根据上图 [left, r - 1] 区域是小于等于key就符合前k小的元素，只要排序到 a + b个数大于等于 k 就行。
当 k <= a，范围缩小：[left, l] 区域找前k小元素
当 k <= a + b，刚好落在key区域，返回答案{nums.begin(), nums.begin() + k}
当 k <= a + b + c，[left, r - 1]符合要求，范围缩小，[r, right] 区域找前 k - a - b 小元素
三、细节总结
1、设待排序数组范围 [left, right]，双指针 l, r ，则 l 初始化是 left - 1, r 初始化是 right + 1，符合一开始没有排序左右两边范围还没有数字。
2、在循环排序时，由于数组范围是 [left, right]，所以遍历指针 i 一开始初始化是 left，结束条件是 i 与 r 相遇。
3、递归结束条件：left >= right，或符合答案就跳出。
4、递归函数接收数组要用引用。