算法導論行使8.3-2理解穩定性

Question

當我得到了答案： http://clrs.skanev.com/08/03/02.html鍛鍊8.3-2， 我不知道如何使用索引專門去解決它。 有人可能會一步一步顯示它或解釋爲什麼是Θ（n）？

這裏是自問自答：

以下哪些排序算法是穩定：插入排序，歸併排序，堆排序，快速排序和？給出一個簡單的方案，使任何排序算法穩定。你的計劃需要多少額外的時間和空間？

穩定：插入排序，歸併排序

不穩定：堆排序，快速排序

我們可以使任何算法穩定由陣列映射到對，的陣列，其中每對中的第一個元素是原始元素，第二個是它的索引。然後我們按字典順序排序。該方案需要額外的Θ（n）空間。

Answer 1

在排序的上下文中，「stable」意味着當包含一些具有等價值的元素的集合被排序時，這些元素相對於彼此保持相同的順序。

因此，通過存儲每個元素的原始索引並將該索引用作排序具有相等主值的元素的次要方法，可以使排序算法穩定。

爲了實現該比較功能（例如<）將實施 所以A <乙返回true如果A.PrimarySortValue < B.PrimarySortValue，並返回（A.OrginalIndex < B.OriginalIndex）時A.PrimarySortValue = = B.PrimarySortValue。否則（當A.PrimarySortValue> B.PrimarySortValue時）它返回false;

這需要爲每個元素存儲一個額外的OriginalIndex值。有n個元素因此Θ（n）需要額外的空間。