任何人都有针对非常慢的写入操作优化的排序算法？

Question

我需要一个排序算法,它在一个预先填充的单个数组上运行,并且仅限于执行一种类型的写操作:

O = 将项目X移动到索引Y.后续位置上的元素移位1个位置.

必须针对尽可能少的操作O优化算法O.读操作比写操作便宜得多.临时助手名单也很便宜.

编辑:将其称为链接列表可能更为正确,因为它的行为,虽然实现对我来说是隐藏的.

背景:

问题是我正在攻击Google API,它只允许我在他们的列表上执行此操作.该操作是Web服务调用.我想尽量减少通话次数.您可以假设排序程序(客户端)在启动之前在内存中有一个列表副本,因此不需要对服务执行读取操作 - 仅写入.在执行服务调用之前,您当然也可以在本地执行任意数量的临时列表操作,包括复制列表或使用现有的.NET排序函数.

我该怎么办？我可以在这里使用已知的算法吗？

尝试失败:

我已经实现了一个哑算法,但它并不适用于所有情况.当列表如下时,它运行良好:

列表A = [2,3,4,5,6,7,8,9,1]

它是这样的:

1. 列表是排序的吗？没有
2. 查找属于位置0的元素:"1"
3. 将元素"1"移动到位置0
4. (新列表状态A1: [1,2,3,4,5,6,7,8,9])
5. 列表是排序的吗？是.结束

......但是当列表是这样的时候,我遇到了麻烦:

清单B = [9,1,2,3,4,5,6,7,8]

1. 列表是排序的吗？没有
2. 查找属于位置0的元素:"1"
3. 将元素"1"移动到位置0
4. (新列表状态B1: [1,9,2,3,4,5,6,7,8])
5. 列表是排序的吗？没有
6. 查找属于位置1的元素:"2"
7. 将元素"2"移动到位置1
8. (新列表状态B2: [1,2,9,3,4,5,6,7,8])
9. ......你可以看到我要去的地方......

Answer 1

计算数组中增长最长的子序列.对序列中不存在的每个元素执行写操作.

编辑:添加一个例子

让输入数组中的数字为1 3 2 7 4 8 6 5 9.增长最快的序列是1 2 4 6 9.计算此序列时,会存储序列中出现的元素的索引.然后直接通过原始数组并找到序列中不存在的元素.在这种情况下,他们是3 7 8 5.对于这些元素中的每一个执行写入操作,将它们放置在适当的位置.所以数组的修改顺序是:

1 2 3 7 4 8 6 5 9 (after writing 3 to appropriate position)
1 2 3 4 8 6 7 5 9 (after writing 7 to appropriate position)
1 2 3 4 6 7 5 8 9 (after writing 8 to appropriate position)
1 2 3 4 5 6 7 8 9 (after writing 5 to appropriate position)