1.颜色划分
75. 颜色分类 - 力扣（LeetCode）https://leetcode.cn/problems/sort-colors/description/分治就是分而治之，把一个非常大的问题，转化为很多相似的子问题。子问题基础上继续划分，直到划分到这个子问题可以快速解决。解决完容易的子问题后相当于解决了父问题，不断向上，这就是分治思想：
这道题要求排序后0都是在前面，1全在中间，2 全在最后。相当于选了一个基准元素1，把小于1的全放左边，大于1的放右边，等于1的放中间即可。解法：三指针。类比移动0算法，这里弄三个指针。定义个i指针用来扫描整个数组，left指针标记0区域的最右侧，right指针标记2区域的最左侧：
在遍历过程中会把数组划分为四个区域：
[0,left]全都是0，[left+1,i-1]都是1，[i,right-1]待扫描的元素，[right,n-1]全都是2。接下来分类讨论(看一般情况)：
i指向0，交换到left+1位置；若left+1位置是1，交换后i和left直接++；若 left+1是0：
交换完后left++，i是0判断过了，所以继续后移。若i指向1，直接i++；若i指向2，和right-1交换，换完right--没问题，但[i,right-1]是待扫描元素，换完后i指向的依旧是带扫描元素，i不++：
可用例子模拟一下，下面实现：
2.快速排序
912. 排序数组 - 力扣（LeetCode）https://leetcode.cn/problems/sort-an-array/description/解法：快速排序(升序)。简单说一下：本质是分治思想，在数组中选个基准元素key，根据基准元素把数组划分为两部分，左边小于等于key，右边大于key，此时选的基准元素的位置就是排序后的位置。接下来把左边和右边按同样思想排序就可以了：
但若里面有重复元素时间复杂度会被退化，选的key每次在最右边：
这选个更优方法用数组分三块来实现快排，分为三个区域：
这样划分完中间这一段区域就不用管了，中间区域在合适的位置。接下来考虑左右区域，继续这样划分。那如何把数组划分成三块：定义i扫描整个数组，left指向左边区域最右侧，right标记大于key的最左侧。下面看分类讨论：根据nums[i]来分类：
接下来递归排左边和右边。这里数组重复时，扫一下就行。下面说个优化，如何选key？我们用随机方式选择基准元素：给个数组，给了左右区间，等概率返回区间上任意一个数：r = rand()；r%(right - left + 1)+left，加left后正好映射到区域里：
下面实现：
3.快速选择算法
215. 数组中的第K个最大元素 - 力扣（LeetCode）https://leetcode.cn/problems/kth-largest-element-in-an-array/description/什么是快速选择算法？前面题把数组划分为三部分：
找第k大的元素时，若能确定第k大的元素在哪个区域，这样有其中两个区域就再不用考虑了。那如何确认第k大的元素在哪个区域呢？设区域元素个数分别为a b c：
1.第k大若落在c区域，那么c大于等于k，此时去[right,r]找第k大。2.若第k大落在b区域，落c区域一定是不成立的，此时c小于k，这时落b区域仅需b+c大于等于k，在中间区域直接返回。3.走到这1 2都不成立，此时去[l,left]找第k - b - c大个元素：
下面实现：
4.最小的k个数
LCR 159. 库存管理 III - 力扣（LeetCode）https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/解法一：容器排序取，NlogN。解法二：堆NlogN。解法三：快速选择算法，O(N)。还是随机选个基准元素key，把数组划分为三部分：
1.a>key，说明最小的k个数在a里面，那么接下来去[l, left]区间找最小的k个元素。2.a+b>=k，说明第k小在[l, right-1]区域间；到这说明1不成立，说明左边区域已在最k小里面，而中间是等于k，那就直接返回。3.1和2都不成立，接下来去[right, r]中找k-a-b个小元素。下面实现：
