使用一个列表理解的冒泡排序

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]

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：
找到了一种更有效的方法来解决这个问题，即使用 slice-assignment:

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

Answer 2

使用列表理解来隐藏 for 循环是一种欺骗，因为理解产生的结果不是排序列表。但是，如果您打算这样做，您可能希望通过在条件中执行交换而不是作为输出值来避免构建 None 元素的列表。

例如：

a = [1, 3, 2, 6, 5, 4]
[_ for n in range(len(a),1,-1) for i in range(n-1) if a[i]>a[i+1] and a.__setitem__(slice(i,i+2),a[i:i+2][::-1])]

隔离元素交换部分，这将给出：

swap = lambda(a,i):a.__setitem__(slice(i,i+2),a[i:i+2][::-1])
[_ for n in range(len(a),1,-1) for i in range(n-1) if a[i]>a[i+1] and swap(a,i)]

与以下内容没有区别：

for n in range(len(a),1,-1):
    for i in range(n-1):
        if a[i]>a[i+1]: 
           swap(a,i)     # same as a[i],a[i+1] = a[i+1],a[i]

列表理解只是编写 for 循环的一种不同方式，实际上并不是 return排序结果。

更符合列表理解的精神是 return 在不影响原始列表的情况下实际排序结果。您可以使用理解中的临时列表来执行元素交换并逐步 return 保证位于正确排序索引的位置：

a = [1, 3, 2, 6, 5, 4]
s = [ b.pop(-1) for b in [list(a)] for n in range(len(a),0,-1) if not [_ for i in range(n-1) if b[i]<b[i+1] and b.__setitem__(slice(i,i+2),b[i:i+2][::-1])] ]
print(s) # [1, 2, 3, 4, 5, 6]

除了 b 用于内部管理交换和 return 排序值外，方法与以前相同。因为保证排序位置始终是 b 中的最后一个，所以交换条件被反转，以便在内部 b 以降序排序，从而在每次迭代中获取最后一项时以升序生成输出.

请注意，所有这些解决方案都未能实现早期退出条件，该条件允许冒泡排序在已经排序的列表和元素接近其排序位置的列表上非常有效（即，当传递中没有交换时停止）。无论元素的原始顺序如何，迭代次数始终为 N*(N+1)/2，始终给出 O(N^2) 的时间复杂度，而不是最坏的情况。

Answer 3

def bubblesort(l):
    [[l.insert(j+1, l.pop(j)) for j in range(i) if l[j] > l[j+1]] for i in range(len(l)-1,0,-1)]
    return l

我使用 l.insert(j+1, l.pop(j)) 来交换列表中的元素。其余的只是嵌套循环。

使用一个列表理解的冒泡排序

Bubble sorting with one list comprehension

python

sorting

algorithm

bubble-sort

python-3.x

示例输入：

示例输出