在这个网页上，我可以阅读：
一些特殊情况算法（在 Programming Pearls 中提到了一个示例）可以比 O(n*log(n)) 更快地对某些数据集进行排序。这些算法不是基于比较被排序的项目，而是依赖技巧。已经表明，没有任何密钥比较算法可以比 O(n*log(n)) 执行得更好。
这是我第一次听说非比较算法。谁能给我一个这些算法的例子，并更好地解释他们如何比 O(nlog(n)) 更快地解决排序问题？该网页的作者在谈论什么样的技巧？
欢迎任何指向论文或其他良好来源的链接。谢谢你。
问问题
901 次
2 回答
8
首先，让我们弄清楚术语：
- 关键比较算法不能比
O(n logn). - 存在其他 -非比较- 算法，给定关于数据的某些假设，可以做得比
O(n logn). 桶排序就是这样一个例子。
举一个第二类的直观示例，假设您知道输入数组完全由零和一组成。您可以遍历数组，计算零和一的数量。让我们称最终计数n0和n1。然后你遍历输出数组，写出n0零和一n1。这是一种O(n)排序算法。
仅仅因为我们利用了数据的特殊结构，才有可能为这个问题提出一个线性时间算法。这与通用的关键比较算法形成对比。这样的算法不需要知道任何关于数据的信息，除了一件事：它们需要知道如何比较任意两个元素的排序键。换句话说，给定任意两个元素，他们需要知道在排序数组中哪个应该排在第一位。
O(n logn)仅使用一种算法就能够以任何可以想象的方式对任何事物进行排序的代价是，没有任何一种算法可以比平均水平做得更好。
于 2012-11-24T08:39:10.200 回答