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

Question

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

是否主要是因为基于非比较的排序算法对非固定长度输入的表现不佳？

例如，假设我有 4 个元素 [1, 100000000000000000024, 3, 5]

基于比较的排序算法将在 4 * log(4) 中解决它。

而基于非比较的排序算法将在 4 * length_of("100000000000000000024") 中解决它，假设我们使用密钥 0 到 9 并使用诸如 LSD 或 MSD 之类的算法。

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

谢谢，韦利

Answer 1

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

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