快速排序 - 使其穩定的條件

如果排序算法使用等號鍵保留任意兩個元素的相對順序，則它是穩定的。在哪些條件下quicksort穩定？快速排序 - 使其穩定的條件

快速排序是穩定的，當沒有項目通過，除非它有一個較小的關鍵。

其他什麼條件使其穩定？

2011-04-27 Paradox

nitpick：這不是保留的_equal_元素的順序，而是_equivalent_元素的順序。規範示例是不區分大小寫的字符串比較：'「a」！=「A」'，但不是「」A「<」a「和」a「<」A「'。 – 2011-04-27 12:33:03

不完全重複，但相關：[Quicksort分區方法的穩定性]（http://stackoverflow.com/questions/1278243/stability-of-quicksort）。 – Dukeling 2017-05-09 20:44:41

那麼，使用O（N）空間而不是使用就地不穩定的實現所使用的O（log N）來實現穩定的快速排列非常容易。當然，使用O（N）空間的快速排序不一定是穩定的，但可以這樣做。

我讀過可以使用O（log N）內存的原地快速排序，但它最終會明顯變慢（並且實現的細節很糟糕）。

當然，您可以隨時瀏覽正在排序的數組並添加一個額外的鍵，這是它在原始數組中的位置。然後快速排序將會保持穩定，您只需在最後刪除額外的鍵。

2011-04-29 16:37:45

賈斯汀皮爾，你可以添加一個鏈接到你已經閱讀的有關野獸實施的文章嗎？ – gen 2016-04-17 15:20:58

quicsort實現如何使用O（log N）內存？它必須存儲它的輸入，它的大小爲N. – Teodor 2017-05-24 17:46:44

Teodor，O（log N）額外的內存。 – 2017-06-06 16:13:43

您可以添加這些到列表中，如果這是你的方法：

2011-04-29 18:32:58 bdares

回答