algorithm - 那么 - 你最近有哪些令人兴奋的算法 "discovered"？

Question

我喜欢阅读新的和聪明的算法。而且我喜欢跳出框框思考，因此欢迎所有计算领域的各种算法。

我不时阅读研究论文以跟上当前的研究并扩大我的视野。我也喜欢学习新技巧。不幸的是，我倾向于只专注于我感兴趣的领域，所以我错过了很多有用的东西。

让我们不要发布主流内容。而是写一些让您觉得特别的事情:“哇 - 现在这是一个聪明的解决方案!”。

Answer 1

我将从每个人都可以使用的东西开始:内省(introspection)排序。 http://en.wikipedia.org/wiki/Introsort

一种新的排序算法，结合了快速排序、插入排序和堆排序的优点。确切地说，它本身并不是一种新算法，而是一种非常巧妙的组合。

您将快速排序的速度提高到快速排序遇到退化的 O(n²) 情况的程度。这几乎是免费的。剩余的分区使用堆排序或合并排序进行排序。这不仅避免了退化的情况，而且还为堆栈使用创建了一个明确定义的上限。

插入排序——像往常一样——关心快速排序过程中遗留下来的所有小分区。

对我来说这是一个新发现，因为我不再为我的应用程序使用快速排序。

我在嵌入式设备上做了很多工作，我确实需要关心堆栈的使用。使用快速排序总是有点冒险，因为它在堆栈上运行失常的可能性微乎其微。即使您知道使用当前数据一切都会好起来的，您也永远不知道以后是否有人将您的代码剪切“粘贴”到另一个项目中并将其用于从未被提及的数据。

多亏了内省(introspection)排序，我现在可以完全控制堆栈的使用并获得性能提升。