前些天在 Bilibili 上看到一个视频(6 分钟演示 15 种排序算法)。好事者戏称:「在视频中,你能听到:冒泡咕噜声、飞机坠地声、暖瓶灌水声、猴子乱叫声等等」,实在搞笑得很。

C++ 的标准模板库有一个很霸气的解读:「标准模板库里的任意算法、数据结构,你找不到一个实现,在所有的情况下都优于标准模板库的实现;否则,它就应该进入标准模板库」。因此,对于排序问题来说,C++ 里的标准模板库中的 std::sort 可想而知是一个在绝大多数情况下都能达到极限性能的排序算法。

前文介绍的内省式排序算法正是 std::sort 采用的算法。但仅有一个理论上优秀的算法是不够的,std::sort 在内部也有很多技巧和权衡值得细细品味。这篇文章尝试来剖析 std::sort

阅读全文 »

又入秋了,天气转凉的时节,患感冒的人总是很多。这篇小文是从「中日友好医院」的宣传画中总结整理出来的,谈一谈感冒的分类及治疗方式,希望能让国人走出「一感冒就吃抗生素」的误区。

阅读全文 »

前作站在信息论的角度,讨论了基于比较的排序算法复杂度的理论下界为 $\Omega(n\log n)$,同时指出了:

每一次判定 $ a < b $,都相当于回答了一次「是否问题」。按照已有的知识,若要尽可能快地完成排序,就要让每一次大小判断的结果落在两种答案之一的概率接近;若不然,则这次比较带来的信息量较小,也就需要更多次的比较来完成排序。

此篇建立在这些知识的基础上,首先探讨以下三个问题,而后引出号称「在所有情况下,都能较快完成排序任务的内省式排序(Introspective Sort)」:

  1. 为什么堆排序一般快不过快速排序?
  2. 快速排序快得无懈可击吗?
  3. 插入排序什么时候快?
阅读全文 »