C++ sort学习笔记

回想起大一的时候打cf…那个时候对C++还不怎么熟悉。。。用sort不会自定义排序方式。。

于是手写快排。。。直接取中间元素没加随机化。。。跪了。。。

后来知道sort怎么写以后。。发现sort是可以通过的。。。

于是我就一直以为sort是带随机化的快排。。。

然而实际上是:

sort在数据量比较大的时候用quick_sort…当分段后的数据量小于某个门槛,为了避免对此递归带来的额外负担。。采取插入排序的策略。。

以及。。。快排在最快情况下还是会到达平方的复杂度。。。

于是有人发明了introsort…中文翻译叫内省排序。。。?

维基百科_introsort

这个算法其实就是。。对于数据量大的时候。。。一开始还是快排。。。但是当递归深度过深时。。用堆排。。。

据说现在的STL一般都是用了introsort….

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz