问非比较排序算法与基于比较排序算法的主要缺点是什么？
EN

Stack Overflow用户

提问于 2013-09-15 20:25:56

回答 1查看 1.3K关注 0票数 0

我试图了解非基于比较的排序算法与基于比较的排序算法的主要缺点。

这主要是因为非基于比较的排序算法在非固定长度输入方面做得不好吗？

假设我有4个元素1,100000000000000000000024，3，5

一种基于比较的排序算法将在4* log(4)中求解。

而非基于比较的排序算法将在4*length_of(“1000000000000000000024”)中求解，前提是我们使用键0到9，并使用诸如LSD或MSD之类的算法。

或者假设我们知道数字介于0到10000000000000000000000024之间，我们可以有从0到1000000000000024之间的键，但这是非常低效率的，因为基于比较的排序算法可以就地完成。

谢谢你，韦利

回答已采纳

发布于 2013-09-15 20:32:49

非比较排序算法通常需要对输入数据(计数排序的小范围整数、桶排序均匀分布的整数等)进行假设。

时间复杂度也常常取决于输入的大小。例如，计数排序取决于范围，以及基数排序。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/18817151

复制

相似问题

问非比较排序算法与基于比较排序算法的主要缺点是什么？EN