基于比较的排序技术的局限性 [英] Limitations of comparison based sorting techniques
问题描述
在大多数需要排序数据的情况下，都选择比较排序.合并排序，快速排序，插入排序和其他比较排序之类的技术可以处理不同的数据类型和效率，而下限为O(nLog(n)).
Comparison sort is opted for in most of the scenarios where data needs to be ordered. Techniques like merge sort, quick sort, insertion sort and other comparison sorts can handle different data types and efficiency with a lower limit of O(nLog(n)).
我的问题是
- 基于比较的排序技术是否有局限性?
- 是否会使用非比较排序技术?
欢呼
推荐答案
您自己或多或少地回答了这个问题.基于比较的排序技术仅限于O(n Log(n))的下限.基于非比较的排序技术不受此限制.非排序算法的普遍问题是必须更好地了解领域，并且由于这个原因，它们不如基于比较的技术那么通用.
You answered it more or less yourself. Comparison based sorting techniques are limited to lower limit of O(n Log(n)). Non-comparison based sorting techniques do not suffer from this limit. The general problem with non-sorting algorithms is that the domain must be better known and for that reason they aren't as versatile as comparison based techniques.
Pigeonhole排序是一个很好的例子，非常简单，只要可能的键值数量接近元素的数量.
Pigeonhole sort is a great and quite simple example which is pretty fast as long as the number of possible key values is close to the number of elements.
这篇关于基于比较的排序技术的局限性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
