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) 时间内完成此操作。