sorting - 稳定排序产生重大影响的可靠示例（或某些业务用例）

Question

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

以前版本的 JAVA 对 collections.sor API 进行了合并排序，这是一种稳定的排序，而对于 Array.sort，使用了快速排序。当前版本的 Java 使用 Tim 排序，这又是一种稳定的排序。所以现在如果你会看到大多数流行的语言，如 Python、Java、Scala 都在使用 Tim Sort。我想知道 Tim Sort 在使用中稳定排序的重要性。推动使用稳定分拣技术的强大动机是什么？

Answer 1

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

快速排序与合并排序还有一个性能问题。通常，归并排序会做更多的移动，但比较少。如果比较开销大于移动开销，则归并排序更快。例如，如果对指向对象的指针数组进行排序（我认为这是 Java 实现对象数组的方式），那么归并排序会更快，因为移动的是指针，而比较的是对象。