稳定的排序算法比不稳定的排序算法慢。 例如，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))
这是对的吗？ 有什么理由更喜欢稳定的类型吗？
除了缓存效果外，当允许使用额外内存时，稳定排序通常比不稳定排序更快。
您从golang链接到的稳定排序不使用额外的空间，因此它必须使用较慢的算法。 当不使用额外内存很重要时，会改用不稳定排序，因为它们在大多数情况下几乎一样快，并且不需要它。
但是，如果您必须为索引分配额外的内存，那么您也可以使用快速稳定排序。 有很多方法可以在 O(N log N) 时间内使用相同的额外空间来完成。
两个数组(原始数据 + 原始数据的索引)上的介绍排序(快速排序 + 堆排序，因此最坏情况的时间复杂度为 O(n log(n))将比合并排序(在单个数组上)花费更长的时间，后者不需要对原始数据 + 索引数组进行排序。
不稳定的快速排序仅比合并排序快 15% 左右。同时对两个数组进行排序会使它比合并排序慢。合并排序的主要缺点是它使用第二个数组。在具有 16 个寄存器的处理器(例如 64 位模式下的 X86)上，4 向合并排序与快速排序一样快。