始终

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

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

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

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

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

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

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

1. 为什么堆排序一般快不过快速排序？
2. 快速排序快得无懈可击吗？
3. 插入排序什么时候快？

进度条是很有用的工具。它可以表示 slides 放映的进度，也可以表示某种技能的熟练度。特别地，在制作简历时，使用「精通」、「熟练」之类的词就不如用一个进度条给所有技能一个统一的标准去衡量。不仅美观，而且直观。

基于比较的排序算法的复杂度下界是 $\Omega(n \log n)$，对于学过算法的人来说，这是一个基本常识。但它是怎么来的呢？