algorithm - 使用稳定排序算法与使用原始索引解决关系的不稳定排序相比有什么优势？

Question

稳定排序算法比不稳定排序慢。例如golang使用 O(n*log(n)*log(n))调用交换元素。

如果我们的目标是保留元素的原始顺序，为什么不对它们全部进行编号 (O(n))，然后使用原始索引进行不稳定排序 (O(n*log(n))) 以解决比较相等的实例。

这似乎更快。

即O(n) + O(n*log(n)) < O(n*log(n)*log(n))

这是正确的吗？有什么理由更喜欢稳定排序吗？

Answer 1

除了缓存效应外，稳定排序在允许使用额外内存时通常更快。

您从 golang 链接到的稳定排序不使用额外空间，因此它必须使用较慢的算法。当不使用额外内存很重要时，会使用不稳定排序，因为它们在大多数情况下几乎一样快并且不需要它。

但是，如果您必须为索引分配额外的内存，那么您不妨使用快速稳定排序。有很多方法可以使用相同数量的额外空间在 O(N log N) 时间内完成。