algorithm - 何时使用非比较排序而不是比较排序

Question

为了避免所有基于比较的排序的 omega(nlogn) 的下界，我们在类里面学习了一堆新的非比较排序。但我不太清楚何时使用哪类排序算法的优缺点。

难道不能调整任何数据集以便可以使用非比较排序算法(基数、桶、键索引)吗？如果是这样，那么比较排序的意义何在？

很抱歉这是一个如此基本的问题，但我真的在网上找不到任何东西。

Answer 1

并非每组项目都可以调整为以有效的方式用于非比较排序。例如，对任意精度数字进行排序需要多次运行桶排序内的循环，从而降低性能。

基数排序世界的问题在于它们必须检查每个被排序项目的每个元素。另一方面，基于比较的排序可以跳过相当数量的子元素(数字、字符等)。例如，当比较函数检查两个字符串时，它会在第一个差异处停止，跳过两个字符串的尾部字符串。另一方面，桶排序必须检查每个字符串中的所有字符^*。

一般来说，追求最好的渐近复杂度并不总是一个好策略:使用明显更复杂的算法带来返回的 N 值通常太高，无法使更复杂的算法实用。例如，快速排序的时间复杂度非常糟糕，但由于其开销非常低，平均而言它击败了大多数其他算法，这使其成为大多数实际情况下的不错选择。

---

^* 在实践中，桶排序的实现避免了查看所有子元素(数字、字符等)的需要，只要桶中的项数达到，就切换到基于比较的排序下降到某个阈值以下。这种混合方法优于普通的基于比较的排序和普通的桶排序。