冒泡排序算法 - 我有错误吗？

Question

我正在关注一个关于冒泡排序的在线网站教程，并决定在查看答案之前自己动手做。

我明白了：

 def bubbleSort(theList):
     i=0
     while i < len(theList)-1:
         if theList[i+1] < theList[i]:
             theList[i],theList[i+1] = theList[i+1],theList[i]
         i=i+1

     return theList

 myList = [13,5,6,2,10,11]
 print(bubbleSort(myList))

但他们的回答是：

 def bubbleSort(alist):
     for passnum in range(len(alist)-1,0,-1):
         for i in range(passnum):
             if alist[i]>alist[i+1]:
                 temp = alist[i]
                 alist[i] = alist[i+1]
                 alist[i+1] = temp

 alist = [54,26,93,17,77,31,44,55,20]
 bubbleSort(alist)
 print(alist)

我遇到的问题是我的答案有效，但我不明白为什么示例答案中多了一行：

  for passnum in range(len(alist)-1,0,-1):

这是什么意思？在其他示例中，我还看到使用了 2 个 for 循环。我的代码有错误吗？似乎有效

Answer 1

您只通过了一次冒泡排序。您的代码是正确的，但它只会将 最大的元素 带到列表的末尾。您应该重复代码 n 次，每次范围减一。

您应该注意到您的代码复杂度为 O(n)，而冒泡排序的复杂度为 O(n^2)。

冒泡排序算法 - 我有错误吗？

Bubble sort algorithm - do i have an error?

python

algorithm

bubble-sort