python - 带有一个列表理解的冒泡排序

Question

我想看看是否可以转换一个BubbleSort函数，例如：

def BubbleSort(l):
    for i in range(len(l)-1):
        for j in range(len(l)-1-i):
            if (l[j]>l[j+1]):
                l[j],l[j+1]=l[j+1],l[j]
    return l

到单行列表理解，可能类似于：

def BubbleSort(l):
    return [something_goes_here for i in range(len(l)-1) for j in range(len(l)-1-i) if (l[j]>l[j+1])]

样本输入：

print(BubbleSort([1,5,-5,0,10,100]))

样本输出

[-5, 0, 1, 5, 10, 100]

标签： pythonpython-3.xalgorithmsortingbubble-sort

Answer 1

基于副作用的解决方案如下所示：

def bubblesort(l):
    [l.append(l.pop(0) if i == len(l) - 1 or l[0] < l[1] else l.pop(1)) for j in range(0, len(l)) for i in range(0, len(l))]
    return l

这将l就地对列表进行排序。

基本思想是同时l视为输入和输出列表。然后可以通过将第一个或第二个元素移动l到末尾来模拟交换。必须将最后一个元素移到末尾而不进行任何比较才能获得新的列表列表。一次迭代 ( [l.append(l.pop(0) if i == len(l) - 1 or l[0] < l[1] else l.pop(1)) for i in range(0, len(l))]) 的可视化示例：

1 3 2 6 5 4 |
  3 2 6 5 4 | 1
    3 6 5 4 | 1 2
      6 5 4 | 1 2 3
        6 4 | 1 2 3 5
          6 | 1 2 3 5 4
            | 1 2 3 5 4 6

在此示例|中，表示原始列表的最后一个元素与已附加的第一个元素之间的分隔符。重复此过程len(l)次数可确保对整个列表进行排序。

请注意，虽然此示例确实执行了冒泡排序，但它的运行时是O(n^3)，因为我们需要在每个步骤中从列表中删除第一个或第二个元素，它在O(n).

编辑：
如果我们这样重写样本迭代，则更容易看出这实际上是上述算法中的冒泡排序：

| 1 3 2 6 5 4
1 | 3 2 6 5 4
1 2 | 3 6 5 4
1 2 3 | 6 5 4
1 2 3 5 | 6 4
1 2 3 5 4 | 6
1 2 3 5 4 6 |

这里分隔符表示列表的结尾，并使用列表的圆形视图。

编辑 2：
找到了一种更有效的方法来解决这个问题，它使用切片分配：

def bubblesort(l):
    [l.__setitem__(slice(i, i + 2), (l[i:i + 2] if l[i] < l[i + 1] else l[i +  1:i - 1:-1])) for j in range(0, len(l)) for i in range(0, len(l) - 1)]
    return l