穩定的排序會產生顯着差異的一個穩定示例（或某個業務用例）

Question

我想知道穩定排序會產生巨大影響的情況。

以前的JAVA版本對collections.sor API進行合併排序，對Array.sort進行穩定排序時，使用了quicksort。 Java的當前版本使用Tim Sort，它又是一個穩定的排序。 所以現在如果你會看到大多數流行的語言，比如Python，Java，Scala都在使用Tim Sort。我想知道Tim Sort在使用中的穩定排序有多重要。 推動使用穩定分揀技術的強大動力是什麼？

Answer 1

對於穩定的排序，數據集一次可以按照一個字段排序，從最低到最高。例如，一些電子表格程序一次有3個字段排序的限制。由於電子表格排序是穩定的，因此可以進行6場排序，首先按照3個最不重要的字段進行排序，然後按3個最重要的字段進行排序。保留原始順序可能是一個理想的副作用。假設數據集按名稱排序，然後該數據集的副本按出生日期排序，具有相同出生日期的元素將保留其原始名稱排序，而無需進行復雜的比較。

快速排序與合併排序也有性能問題。通常情況下，合併排序可以做更多的動作，但比較少。如果比較開銷大於移動開銷，則合併排序更快。例如，如果將一個指向數組的指針排序（這是我認爲Java實現一個對象數組的方式），那麼合併排序可以更快，因爲被移動的是指針，並且比較的是對象。