快速排序 quick sort

快速排序是二叉树的前序遍历

快排选择一个基准点，通过讲数组整理成两部分（前半小于 pivot 后半大于 pivot）找到基准点在数组中的位置，再递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组所有元素都找了自己的位置

func quickSort(nums []int, low, high int) {
	// 前序遍历位置
	p := partition(nums, low, high) // 通过交换元素构建分界点 p
	quickSort(nums, low, p-1)
	quickSort(nums, p+1, high)
}

• 版本 1：基本快排：把等于切分元素的所有元素分到了数组的同一侧，可能会造成递归树倾斜；
• 版本 2：双指针快排：把等于切分元素的所有元素 等概率 地分到了数组的两侧，避免了递归树倾斜，递归树相对平衡；
• 版本 3：三指针快排：把等于切分元素的所有元素挤到了数组的中间，在有很多元素和切分元素相等的情况下，递归区间大大减少。

之所以快排有这些优化，起因都是来自「递归树」的高度。关于「树」的算法的优化，绝大部分都是在和树的「高度」较劲。类似的通过减少树高度、使得树更平衡的数据结构还有「二叉搜索树」优化成「AVL 树」或者「红黑树」、「并查集」的「按秩合并」与「路径压缩」。

写对「快速排序」的技巧：保持「循环不变量」，即定义的变量在循环开始前、循环过程中、循环结束以后，都保持不变的性质

循环不变量

**「循环不变量」**是证明算法有效性的基础，更是写对代码的保证，遵守循环不变量，是不是该写等于号，先交换还是先 ++ ，就会特别清楚，绝对不会写错，可以将遵守的「循环不变量」作为注释写在代码中

对 循环不变量 的简单认识：

• 变量的值是变化的，但是保持不变的性质，就是循环不变量
• 这里的「量」是一些人为定义的、可以判断真假的语句，在循环开始前、循环的过程中、循环结束以后，都为真
• 这里的「循环」是广义上的，并不一定指「循环」，也有可能是在「递归」的过程中

75. 颜色分类

进阶：想出一个仅使用常数空间的一趟扫描算法，即一次遍历把数组分成三个部分（partition 过程

不同的循环不变量定义决定了：初始化时变量的取值、循环的过程中操作的先后顺序、循环结束的条件