改變一個黑箱陣列排序算法是一個穩定的算法

Question

讓Sort1是一個給定的算法和一個給定的數組。 Sort1以f（n）的時間運行。 我需要使用Sort1來創建一個新的穩定算法Sort2，它將在f（n）+ O（n）的時間內運行。

我有辦法解決我的朋友建議：

• 創建A.
• B中每個數字更改爲一對夫婦（數，指數），其中數是多少的克隆陣列B（元素），索引是它的索引（在A中的位置）。
• 在乙組分給它的每一個元素是在排序的相同數字的每一個順序A. A.上
• 運行SORT1相應的元素，在運行Flash SORT1將由指數排序閃光每個元素。

是他的解決方案嗎？你有什麼建議嗎？ 謝謝！

Answer 1

製作你的副本，但是然後創建一個新的比較函數，它使用原始數據作爲主鍵（可能甚至使用原始比較函數進行比較），如果相同，則進行二次比較在數組中的原始位置。