9

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

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

该算法必须针对尽可能少的操作 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. ...你可以看到我要去哪里...
4

3 回答 3

9

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

编辑：添加一个例子

让输入数组中的数字为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)
于 2012-10-05T15:17:06.840 回答
2

在本地对数组进行排序。保留原件的副本。

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

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

于 2012-10-05T15:13:30.870 回答
2

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

对于您的示例：

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

为古怪的伪代码风格道歉，我试图让它足够窄，以至于代码块不需要滚动条。

于 2012-10-05T16:48:30.530 回答