快速冒泡排序

Question

def bubble(lst):
    swap = 'True'
    counter = 0
    n = len(lst)
    m = len(lst)
    while swap == 'True':
            for j in range(n-1):
                    if lst[j] > lst[j+1]:
                            lst[j],lst[j+1] = lst[j+1],lst[j]
                            counter += 1
                            swap = 'True'
                    else:
                            swap = 'False'
            n = n - 1
    return counter

如何缩短此函数所需的时间，因为我想在更大的列表上使用它。

Answer 1

更改算法。

使用合并排序或快速排序。

冒泡排序是 O(n*n)。 它存在的唯一原因是向学生展示他们不应该如何对数组进行排序:)

归并排序是最坏情况的 O(n log n)。

快速排序最坏情况为 O(n * n)，平均情况为 O(n log n)，但具有“低常数”，因此它通常比合并排序更快。

在网上搜索它们。

如果我没有错的话...（如果我愿意的话请不要对我发怒）...我想我明白你想做什么：

def bubble(lst):
    n = len(lst)
    while True
        newn = 0
        for i in range(1, n-1):
            if lst[i-1] > lst[i]:
                lst[i-1],lst[i] = lst[i],lst[i-1]
                newn = i
                counter += 1
        if newn <= 0:
            return counter
        n = newn

但是复杂度始终为 O(n * n)，因此您不会注意到任何重要的差异。

例如：

如果您的列表有 2000 个项目并且您使用冒泡排序，则 O(2000 * 2000) = 4000000 循环步骤。这是巨大的。

O(2000 * log2 2000) = 大约 21931 个循环步骤，这是可以管理的。

Answer 2

已知最快的冒泡排序称为鸡尾酒摇床排序。

A = [5, 1, 4, 2, 8]

def cocktail_shaker_sort():
  I = 0
  backwards = False
  swapped = True
  beginI = 0
  endI = len(A) - 2
  newBeginI = endI
  newEndI = 0

  while True:
    if I > endI:  # Turn back
      if not swapped:  # No swaps since the previous turn
        break
      swapped = False
      backwards = True

      # The elements after `newEndI` are in correct order
      endI = newEndI - 1
      I = endI
      newEndI = beginI
    else:  # Turn forward
      if I < beginI:  # Turn forward
        if not swapped:  # No swaps since the previous turn
          break
        swapped = False
        backwards = False

        # The elements before `newBeginI` are in correct order
        beginI = newBeginI + 1
        I = beginI
        newBeginI = endI

    if A[I] > A[I + 1]:
      swapped = True
      A[I + 1], A[I] = A[I], A[I + 1]  # Swap (combined assignment)

      if backwards:
        newBeginI = I
      else:
        newEndI = I

    if backwards:
      I -= 1
    else:
      I += 1
      
  return A

cocktail_shaker_sort()
print(A)

详情请参阅维基百科。

我已经删除了内部循环。这并没有优化任何东西。只是想尝试一下。这是一个 Javascript 版本：

var A = [5, 1, 4, 2, 8], iter = 0, I = 0
var backwards = false, swapped = true
var beginI = 0
var endI = A.length - 2;
var newBeginI = endI;
var newEndI = 0;

while (true) {
  if (I > endI) { //turn back
    if (!swapped) break; //no swaps since prev turn
    swapped = false
    backwards = true

    //the elements after `newEndI` are in correct order
    I = endI = newEndI - 1;
    newEndI = beginI;
  }
  else if (I < beginI) { //turn forward
    if (!swapped) break; //no swaps since prev turn
    swapped = false
    backwards = false

    //the elements before `newBeginI` are in correct order
    I = beginI = newBeginI + 1;
    newBeginI = endI;
  }

  var a = A[I], b = A[I + 1]
  if (a > b) {
    A[I + 1] = a; A[I] = b; //swap
    swapped = true

    if (backwards) newBeginI = I;
    else newEndI = I;
    console.log("swap " + a + " > " + b + "\n" + A)
  }
  else console.log("skip " + a + " < " + b + "\n" + A)

  if (backwards) I--; else I++

  iter++
}

console.log(A)