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

比较排序在大多数需要排序数据的场景中选择。诸如合并排序，快速排序，插入排序和其他比较排序等技术可以用O（nLog（n））的下限处理不同的数据类型和效率。基于比较的排序技术的局限性

我的问题是

是否有基于排序技术比较没有任何限制？
任何一种情况下，将使用非比较排序技术？

欢呼

来源

2009-04-26 Arnkrishn

你回答或多或少自己。基于比较的排序技术限于O（n Log（n））的下限。基于非比较的排序技术不受此限制。非排序算法的一般问题是该域必须更为人知，因此它们不像基于比较的技术那样多功能。

Pigeonhole sort是一个很好很简单的例子，只要可能的键值数量接近元素数量，它就会非常快速。

来源

2009-04-26 22:57:29

显然，比较排序的局限性在于时间因素 - some are better than others，但是如果数据集足够大，它们在某个点上会变得太慢。诀窍是根据您正在排序的数据的种类和组合来选择正确的。

非比较排序是基于忽略数据的其他因素，例如counting sort将通过检查每个元素来排序数据集合，而不是将其与集合中的任何其他值进行比较。如果您有一个整数集合，对排序进行排序是非常有用的，如果您有一个整数集合，它将通过将所有元素的值设为1并将它们放入目标中，然后将所有元素的值为2等等（好吧，它使用“稀疏”阵列快速缩放收集并重新排序值，留下空白，但这是基本原理）

来源

2009-04-26 22:59:43 gbjbaanb

很容易看出，为什么比较排序需要关于N log N比较。有N！如我们所知，ln（N！）大约是N ln N - N + O（ln N）。在大O符号中，我们可以忽略低于N ln N的项，并且因为ln和log仅相差恒定，我们得到最终结果O（N log N）

来源

2012-07-29 04:14:05

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

回答

相关问题