logo标签列表

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

sorting
5

在大多数需要排序数据的情况下，选择比较排序。像归并排序、快速排序、插入排序和其他比较排序技术可以处理不同的数据类型，并具有O(nLog(n))的下限效率。

我的问题是：

  1. 比较排序技术有哪些限制？
  2. 是否存在任何非比较排序技术可用的场景？

谢谢！

3个回答
3
您自己已经回答了这个问题。基于比较的排序技术受到O(n Log(n))下限的限制。而非基于比较的排序技术则不受此限制。非排序算法的一般问题在于必须更好地了解域，因此它们不如基于比较的技术灵活多样。
鸽巢排序是一个很好而且相当简单的例子，只要可能的关键值数接近元素数，就可以非常快速地进行排序。 （参见维基百科）
3
显然，比较排序的限制是时间因素 - 有些比其他的好, 但如果数据集足够大，它们在某一点上都会变得太慢。关键是根据你要排序的数据的类型和混合选择正确的排序方法。

非比较排序基于忽略数据的其他因素，例如计数排序将通过检查每个元素 - 而不是将其与集合中的任何其他值进行比较来对数据集进行排序。如果你有一组整数，计数排序很有用，它会将所有值为1的元素放入目标的第一个位置，然后将所有值为2的元素等等排序（好吧，它使用一个“稀疏”数组来快速遍历集合并重新排序值，但这就是基本原理）。

0

很容易看出，为什么比较排序需要约N log N次比较。有N！种排列方式，而我们知道ln（N！）大约等于N ln N - N + O(ln N)。在大O符号中，我们可以忽略低于N ln N的项，因为ln和log只相差一个常数，所以我们得到最终结果O（N log N）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接