对数器：我有一个待测的更优秀的方法A，有一个暴力破解方法B
然后用一个函数生成随机样本，把样本放到方法A和方法B里面，判断是否彼此相等，来判断方法A是否正确
跑几千万次都相等，那么可以说方法A是对的

master公式：T(N) = a * T(N/b) + O(N^d)
--> T(N/b)：子问题的时间规模
--> a：子问题调了多少次
--> O(N^d)：除了子问题之外的时间规模
1. 当 log_b_(a) < d：O(N^d)
2. 当 log_b_(a) > d：O(N^(log_b_(a))))
3. 当 log_b_(a) = d：O(N^d * log N)


基于比较的排序：
1. 时间复杂度在O(n*lgn)以下的算法是否有？目前没有。
2. 时间复杂度在O(n*lgn)的情况下，空间复杂度低于O(n)且算法稳定是否有？目前没有。
目前的瓶颈是时间复杂度O(n*lgn)，在要求稳定性的情况下，O(n)是瓶颈(归并排序)。
归并排序可以让空间复杂度变成O(1)————归并排序 内部缓存法，但是之后不再稳定。
快速排序还想要稳定性，就是——01 stable sort。
// 有一道题，奇数放在数组左边，偶数放在数组右边，还要求原数组次序不变
// 在快排中，partition中就是 0 1 划分，奇数在左边，偶数在右边。

工程上对排序的改进：
1. 考虑O(n*lgn)和O(n^2)的各自优势；
    比如在大样本上利用快排的调度优势；在小样本上利用插入排序。
    因为在样本是很小的时候，N^2的瓶颈已经非常不明显了。
    这种叫“综合排序”。
2. 稳定性的考虑。
    在基础类型的时候，会使用快排；如果是非基础类型的时候，就使用归并。
    这是为了保持稳定性，因为不清楚数据的稳定性是否需要。