具有列表理解功能的气泡排序 [英] Bubble sorting with one list comprehension

问题描述

我想看看是否有可能转换 BubbleSort 函数，例如：

I'd like to see if it would be possible to convert a BubbleSort function, such as:

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

到单层列表理解，也许类似于：

to a one-liner list comprehension, maybe similar to:

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])]

样本输入：

Sample Input:

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

样本输出

Sample Output

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

推荐答案

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

A solution based on side-effects looks like this:

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 进行就地排序。

This will sort the list l in-place.

基本思想是将 l 视为输入列表和输出列表。然后可以通过将 l 的第一个或第二个元素移到末尾来模拟掉期。必须将最后一个元素移到末尾，而不进行任何比较以获得新的列表。一个迭代的可视示例（ [l.append（l.pop（0），如果i == len（l）-1或l [0] ）中的i：

The basic idea is to treat l as both the input and output-list. Swaps can then be emulated by either moving the first or the second element of l to the end. The last element must be moved to the end without any comparison to get a new list list. A visual example of one iteration ([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）次可确保对整个列表进行排序。

In this example | denotes the separator between the last element of the original list and the first element that was already appended. Repeating this process len(l) times guarantees that the entire list is sorted.

请注意，尽管此示例执行冒泡排序，其运行时为 O（n ^ 3），因为我们需要在每个步骤中从列表中删除第一个或第二个元素，该元素在<$ c中运行$ c> O（n）。

Note that while this example does perform a bubblesort, it's runtime is O(n^3), since we need to remove the first or second element from the list in each step, which runs in O(n).

编辑：

变得更容易看到这实际上是冒泡的根据上述算法，如果我们这样重写样本迭代：

It becomes more easy to see that this is actually bubblesort from the above algorithm, if we rewrite the sample-iteration as such:

| 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 |

此处的分隔符表示列表的末尾，并使用列表的循环视图。

Here the separator denotes the end of the list and a circular view of the list is used.

编辑2：

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

EDIT 2:
Found a more efficient way to solve this that uses 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

这篇关于具有列表理解功能的气泡排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！