有人为非常慢的写入操作优化了排序算法吗？

Question

我需要一个排序算法，它对单个预先填充的数组进行操作，并且仅限于执行一种类型的写操作：

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

该算法必须针对尽可能少的运算次数进行优化。读取操作比写操作便宜得多。临时助手列表也很便宜。

编辑：也许称它为链接列表更正确，因为它的行为，尽管对我来说实现是隐藏的。

背景：

问题是，我使用的是一个Google，它只允许我在他们的列表上执行这个操作。该操作是一个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. 名单排序了吗？是。结束

...But当列表是这样的时候，我就陷入麻烦了：

列表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. ...you能看到我要去的地方..。

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)

Answer 2

对数组进行本地排序。保存原件一份。

使用LCS距离计算原始数组和排序版本之间的最佳编辑序列；这是不允许替换的Levenshtein距离的变体。一个简化的Levenshtein动态规划算法可以用来计算LCS距离。查看diff等程序的源代码，了解如何从动态编程表中获取编辑序列。

现在您有了一个编辑序列，这意味着要执行一个插入和删除列表，以将原始数组转换为排序版本。执行插入。(您可以跳过删除操作，因为它们将由操作O执行，但请注意，数组中的索引会因此而发生变化，因此必须对其进行补偿。)

Answer 3

搜索最长的排序子序列，并将每个未排序的元素移到正确的位置。

关于你的例子：

start: 2,3,4,5,6,7,8,9,1 (O = 0)
LSS:   2,3,4,5,6,7,8,9
step:  1,2,3,4,5,6,7,8,9 (O = 1)

start: 9,1,2,3,4,5,6,7,8 (O = 0)
LSS:   1,2,3,4,5,6,7,8
step:  1,2,3,4,5,6,7,8,9 (O = 1)

我的一个：

start: 9,3,1,7,2,8,5,6,4 (O = 0)
LSS:   1,2,5,6
step:  3,1,7,2,8,5,6,9,4 (O = 1)
LSS:   1,2,5,6,9
step:  1,7,2,3,8,5,6,9,4 (O = 2)
LSS:   1,2,3,5,6,9
step:  1,2,3,8,5,6,7,9,4 (O = 3)
LSS:   1,2,3,5,6,7,9
step:  1,2,3,5,6,7,8,9,4 (O = 4)
LSS:   1,2,3,5,6,7,8,9
step:  1,2,3,4,5,6,7,8,9 (O = 5)

你需要一个算法来识别LSS。您只需要使用它一次，在您拥有它之后，您可以在排序时将元素插入其中。

伪码：

function O(oldindex, newindex):
    # removes oldindex from list, shifts elements, inserts at newindex

function lss(list):
    # identifies the LSS of a list and returns it in a cheap temporary list

function insert(index, element, list):
    # inserts specified specified element into specified index in specified list
    # elements at and after specified index are shifted down to make room

function sort(input):
    lss_temp_list = lss(input)                     # get lss of input list

    do until lss == input:
    old = any(index where (input[index] not in lss)# item in input; not in lss

                                                   # getting new index is uglier
    nl = min(X where (X > input[old] and X in lss))# next lowest element in lss
    nh = max(X where (X < input[old] and X in lss))# next highest element in lss

    new = any(index                                # index of next lowest/highest
          where ((input[index + 1] == nl and nl exists)
              or (input[index + 1] == nh and nh exists))

    O(old, new)                                    # list shift

    il = min(index where (lss[index] > input[new]))# index of next lowest in lss
    ih = max(index where (lss[index] < input[new]))# index of next highest in lss
    i = any(X where (X == il or X == (ih + 1)))    # index to insert element
    insert(i, input[new], lss)                     # add new element to lss
    repeat
    return input

对于不稳定的伪代码风格，我很抱歉，我试图使它足够窄，使代码块不需要一个滚动条。