python - 遵循算法的冒泡排序

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 个多小时，但我无法让它工作:

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       #if this pair is out of order
       if A[i-1] > A[i] then
         # swap them and remember something changed
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

我有点卡在了 repeat & until 阶段。我知道我必须使用 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

与它上面的版本一样，只是它利用了这样一个事实，即每次运行后，保证对最后的 X 条目进行排序。

这样设想可能更容易:

procedure bubbleSort(someList):
  while someList is not sorted:
    loop over all elements in the list:
      if the current item is larger than the next item:
        swap items

冒泡排序基本上是重复扫描列表，如果两个元素相对乱序则交换它们。你只需要这样做。

唯一有点棘手的部分是“while someList 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