python - 给定一个未排序的 python 列表，如何找到对其进行排序所需的最小移动集

Question

我有一个存储在远程数据库中的项目列表，这些项目可能未排序，我想对它们进行排序。数据库接受以下形式的命令:

move item1 before item2
move item3 after item2

因此，给定一个表单列表:

[1,3,2,7,6,0,4]

...如何获得移动顺序:

move 2 before 3
move 7 after 6
move 0 before 1
move 4 before 6

我假设对冒泡排序算法的修改会起作用，但我特别在寻找仍然是 pythonic 且生成最少移动命令的最有效实现。

更新:列表长 1000-10000，所有项目都是唯一的 - 没有重复。在任何给定时间，只有极少数元素(1-10 件)会出现在错误的位置。时间是一个问题 - 它应该需要几秒钟，而不是几分钟 - 但它不必非常快。

更新 2:我还想每个项目只移动一次

Answer 1

由于要减少移动序列的数量，我能想到的最优方法是对排序列表使用二分查找来确定每个元素的插入点。如果任何元素已经在其正确位置，则无需移动它。

这将生成 n - d 序列移动，其中 n 是元素的数量，d 是其正确位置的元素数量.

• 对于一个已经排序的列表，序列移动的次数是n - d = n - n = 0
• 对于所有元素都在错误位置的列表，序列移动次数为 n - d = n - 0 = n

实现

def gen_move(seq):
    from bisect import bisect_left
    out = seq[0:1]
    for elem in seq[1:]:
        index = bisect_left(out, elem)
        if seq[index] != elem:
            if index == 0:
                print "Move {} before {}".format(elem, out[index])
            else:
                print "Move {} after {}".format(elem, out[index - 1])
        out.insert(index, elem)
    print out

演示

gen_move([1,3,2,7,6,0,4])
Move 2 after 1
Move 6 after 3
Move 0 before 1
Move 4 after 3
[0, 1, 2, 3, 4, 6, 7]

gen_move(range(10)[::-1])
Move 8 before 9
Move 7 before 8
Move 6 before 7
Move 5 before 6
Move 4 before 5
Move 3 before 4
Move 2 before 3
Move 1 before 2
Move 0 before 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

gen_move(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

性能

In [5]: %timeit gen_move(range(10000, 0, -1))
10000 loops, best of 3: 84 us per loop

时间复杂度

sum(1 ln 1 + 2 ln 2 + 3 ln 3 + ..... n ln n) < O(n ln n)

空间复杂度

O(n)