将一个黑盒数组排序算法转换为稳定算法

Question

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

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

- 创建一个克隆数组B。 - 将B中的每个数字更改为一对数字（number，index），其中number是数字（元素），index是它在A中的索引（位置）。 - B中的每个元素都指向其在A中对应的元素。 - 在A上运行Sort1。 - 对于排序后A中相同数字的每个序列，在flash上运行Sort1，这将按每个元素的索引对flash进行排序。

他的解决方案正确吗？你有什么建议吗？谢谢！

- Shai Balassiano

---

对不起，flash是什么？ - B. Decoster

Answer 1

首先复制原始数据，然后创建一个新的比较函数，将原始数据作为主键（可能还使用原始比较函数进行比较），如果相等，则基于原始数组中的位置进行二次比较。

- Jerry Coffin