按算法冒泡排序

Question

我正在尝试用python实现一个气泡排序的代码：
我设法用double for编写了一个代码，它运行得很好。在

A=[43,21,12,80,3,2,35]
lengthOfList = len(A)
for i in range (lengthOfList):
    for k in range(lengthOfList-1, i,-1 ):
        if ( A[k - 1]> A[k]):
            temp = A[k]
            A[k] = A[k-1]
            A[k-1] = temp
print A

我正在尝试采用此算法登录3个多小时了，但是，我不能让它工作：

^{pr2}$

我有点困在重复&直到阶段。我知道我必须使用while，但是我无法理解如何使用while来实现它

Answer 1

你没有正确地改编维基百科的代码

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

jsut是否与上面的版本相同，只是它利用了这样一个事实：每次运行之后，最后一个X条目的排序得到保证。在

这样的设想可能更容易：

^{pr2}$

Bubble sort基本上会反复扫描列表，如果两个元素的顺序相对不一致，就交换它们。你只需要这么做。在

唯一棘手的部分是“whilesomelist is not sorted”；有两种方法来处理这个问题。一种方法是编写一个函数，简单地告诉您列表是否已排序，您可以这样做：

def isListSorted(l):
  for i in range(len(l)-1):
    if l[i] > l[i+1]: return False

  return True

或者，您知道如果它能够在不交换任何元素的情况下遍历整个列表，那么它将被排序，因此您可以使用flag来跟踪它

def bubbleSort(l):
  isSorted = False
  while not isSorted:
    isSorted = True
    for i in range(len(l)-1):
      if l[i] > l[i+1]:
        isSorted = False
        l[i], l[i+1] = l[i+1], l[i]

或者，如果您想使用上述函数

def bubbleSort2(l):
  while not isListSorted(l):
    for i in range(len(l)-1):
      if l[i] > l[i+1]:
        l[i], l[i+1] = l[i+1], l[i]

并不是说第一个解决方案更快，因为它不会在每个循环开始时循环检查整个列表，以检查它是否已排序，但这与优化无关，因为您正在寻找气泡排序。在

如果你还在为添加页面上提到的优化而烦恼，这是一个简单的任务

def bubbleSort(l):
  isSorted = False
  n = len(l)-1
  while not isSorted:
    isSorted = True
    for i in range(n):
      if l[i] > l[i+1]:
        isSorted = False
        l[i], l[i+1] = l[i+1], l[i]
    n-=1


def bubbleSort2(l):
  n = len(l)-1
  while not isListSorted(l):
    for i in range(n):
      if l[i] > l[i+1]:
        l[i], l[i+1] = l[i+1], l[i]
    n-=1