谈谈内省式排序算法 | 始终

[Liam0205]

https://liam.page/2018/08/29/introspective-sort/

前作站在信息论的角度，讨论了基于比较的排序算法复杂度的理论下界为 $\Omega(n\log n)$，同时指出了： 每一次判定 $ a < b $，都相当于回答了一次「是否问题」。按照已有的知识，若要尽可能快地完成排序，就要让每一次大小判断的结果落在两种答案之一的概率接近；若不然，则这次比较带来的信息量较小，也就需要更多次的比较来完成排序。 此篇建立在这些知识的基础上，首先探讨以下三个问

[muyuuuu]

今天刚看到，在这里统一回复下吧：

你这篇博客里的一句话：插入排序某种意义上是最生动的排序算法了。在玩扑克牌的时候，大多数人都会使用插入排序的办法，将分派到自己的扑克牌按顺序整理好。

这句话，像不像是桶排序？之前上课出过一个例题：

有一个序列：12512115，整理为从小到大排列的顺序，至少需要移动几次。当时想的是前面是1，中间是2，后面是5，然后就是桶排序，也可以类比到打扑克的情景吧。

此外，可能是我插入排序实现的问题，这也是我第一次写计算机算法的代码，初次尝试多多不足。

比较排序算法中使用了信息熵，好像是目前我见过的很有意思的一股清流。我已经不好意思说过我上了两学期的算法课了，第一学期是数据结构，第二学期是算法分析与设计，无地自容。

另外，STL只是听说过，平时也很少写C++的程序（基本不写）。搞算法的同学给我推荐过这个，不知深入的研究是否有好处。总感觉我现在写博客是不是有点早（大三），看你的博客发现自己完全还是不够火候，写的内容过于浅显。不过该考研了，大概是ML的方向，暂时没时间折腾这些我感兴趣的东西。。。

[muyuuuu]

对了，我之前给我们学校参加比赛的同学写过一份美赛的latex模板，zepinglee说如果感觉之前的模板不够好想要改进的话，最好联系下作者，今天终于发现你是作者哈哈哈。等我整理一下，大概.......很长时间后能不能帮我看看。。。（虽然我写的压根不是模板，只是把比赛需要的格式写进了.tex文件。比如第一页摘要页有个大表格，我就开始在.tex文件里画个表格出来）。。。

[Liam0205]

@muyuuuu 排序的话，桶排序和插入排序等是有明显不同的。桶排序的基本操作是「是不是」的问题，「是，则放入这个桶」。插入排序（包括快排、堆排）都是基于比较的算法，它们的基本操作是「这两个数哪个大」。

我已经不太玩 LaTeX 了，@zepinglee 出来接锅……

[zepinglee]

ustc 和 thu 的锅我都已经背不动了， @muyuuuu 不妨在 https://github.com/Liam0205/mcmthesis/issues 列一下 feature requests.