Note: This article is available in Chinese only. 本文暂无英文版本。
View original
回想起大一的时候打cf…那个时候对C++还不怎么熟悉。。。用sort不会自定义排序方式。。
于是手写快排。。。直接取中间元素没加随机化。。。跪了。。。
后来知道sort怎么写以后。。发现sort是可以通过的。。。
于是我就一直以为sort是带随机化的快排。。。
然而实际上是：
sort在数据量比较大的时候用quick_sort…当分段后的数据量小于某个门槛，为了避免对此递归带来的额外负担。。采取插入排序的策略。。
以及。。。快排在最快情况下还是会到达平方的复杂度。。。
于是有人发明了introsort…中文翻译叫内省排序。。。？
这个算法其实就是。。对于数据量大的时候。。。一开始还是快排。。。但是当递归深度过深时。。用堆排。。。
据说现在的STL一般都是用了introsort….