设 Sort1 为给定算法,A 为给定数组。 Sort1 在 f(n) 的时间内运行。 我需要使用将在 f(n)+O(n) 时间内运行的 Sort1 创建一个新的稳定算法 Sort2。
我有一个 friend 建议的解决方案:
- 创建 A 的克隆阵列 B。
- 将 B 中的每个数字更改为一对 (number,index),其中 number 是数字(元素),index 是它的索引(A 中的位置)。
- B中的每个元素都指向它在A中的对应元素。
- 在 A 上运行 Sort1。
- 对于已排序的 A 中的每个相同数字序列,在闪存上运行 Sort1,这将根据每个元素的索引对闪存进行排序。
他的解决方案对吗?你有什么建议吗? 谢谢!
最佳答案
制作你的副本,然后创建一个新的比较函数,它使用原始数据作为主键(甚至可能使用原始比较函数来进行比较),如果相等,让它根据数组中的原始位置。
关于algorithm - 将黑盒数组排序算法更改为稳定算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6536710/