大多数需要对数据进行排序的场景都会选择比较排序。合并排序、快速排序、插入排序和其他比较排序等技术可以处理不同的数据类型,并且效率的下限为 O(nLog(n))。
我的问题是
- 基于比较的排序技术有任何限制吗?
- 有哪些场景会使用非比较排序技术?
cheers
你自己或多或少已经回答了。基于比较的排序技术仅限于 O(n Log(n)) 的下限。非基于比较的排序技术不受此限制。非排序算法的普遍问题是必须更好地了解该领域,因此它们不像基于比较的技术那么通用。
鸽巢排序 http://en.wikipedia.org/wiki/Pigeonhole_sort是一个很棒且非常简单的示例,只要可能的键值的数量接近元素的数量,它就相当快。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)