基于比较的排序技术的局限性

Question

在需要订购数据的大多数情况下,都会选择比较排序.合并排序,快速排序,插入排序和其他比较排序等技术可以处理不同的数据类型和效率,下限为O(nLog(n)).

我的问题是

1. 基于比较的排序技术是否有任何限制？
2. 是否会使用非比较排序技术的任何场景？

干杯

Answer 1

你自己或多或少已经回答了。基于比较的排序技术仅限于 O(n Log(n)) 的下限。非基于比较的排序技术不受此限制。非排序算法的普遍问题是必须更好地了解该领域，因此它们不像基于比较的技术那么通用。

鸽巢排序是一个很棒且非常简单的示例，只要可能的键值的数量接近元素的数量，它就相当快。