将黑盒数组排序算法改为稳定算法

Question

令Sort1为给定算法,A为给定数组.Sort1以f(n)的时间运行.我需要使用Sort1创建一个新的稳定算法Sort2,它将在f(n)+ O(n)的时间内运行.

我的朋友建议我有一个解决方案:

• 创建A的克隆数组B.
• 将B中的每个数字更改为一对(数字,索引),其中数字是数字(元素),索引是它的索引(A中的位置).
• B中的每个元素都指向它在A中的对应元素.
• 在A.上运行Sort1
• 对于排序A中相同数字的每个序列,在flash上​​运行Sort1,它将按每个元素的索引对flash进行排序.

他的解决方案对吗？你有什么建议吗？谢谢!

Answer 1

复制,然后创建一个新的比较函数,使用原始数据作为主键(可能甚至使用原始比较函数进行比较),如果相同,让它根据原始位置进行二次比较在数组中.