一个可靠的示例(或一些业务用例)，其中稳定的排序会产生显著的差异。

Question

我想知道稳定排序会产生巨大影响的场景。

以前版本的JAVA有合并排序的collections.sor API，这是一个稳定的排序，而对于Array.sort，快速排序被使用。当前版本的Java使用Tim，这也是稳定的排序。因此，现在如果您看到大多数流行的语言，如Python、Java、Scala都在使用Tim。我想知道提姆排序在使用上是稳定排序的，它有多重？驱动使用稳定排序技术的强烈动机是什么？

Answer 1

有了稳定的排序，数据集可以一次按一个字段排序，从最不重要到最重要。例如，一些电子表格程序一次按3个字段排序是有限制的。由于电子表格排序是稳定的，那么一个6字段排序是可能的，首先按3个最不重要字段排序，然后按3个最重要字段进行排序。保持原来的顺序可能是一种预期的副作用。假设数据集按名称排序，然后按出生日期对该数据集的副本进行排序，具有相同出生日期的元素将保留其原始名称顺序，而不需要进行复杂的比较。

快速排序和合并排序也存在性能问题。通常，合并排序会产生更多的移动，但相比较而言则更少。如果比较开销大于移动开销，合并排序将更快。例如，如果对指向对象的指针数组进行排序(我认为这是Java实现对象数组的方式)，那么合并排序可能会更快，因为正在移动的是指针，比较的是对象。