短冒泡和冒泡排序的实现

Question

上面URL写的很清楚，short bubble是对冒泡排序的一种修改，减少pass的次数。因此，在我实现这两种算法时，我添加了一个计数器来计算通过次数，令人惊讶的是两者都具有相同的编号。通行证。这是我的代码：

def bubbleshort(mylist):
    flag= True
    passnum= len(mylist) -1
    counter = 0
    while flag and passnum > 0:
          flag = False

          for element in range(passnum):
                if mylist[element] > mylist[element + 1]:
                flag = True

                temp= mylist[element]
                mylist[element]= mylist[element+1]
                mylist[element + 1] = temp
                counter += 1
          passnum -= 1
    return mylist, counter

def bubble(yourlist):
    count=0
    for i in range(len(yourlist)-1, 0, -1):
        for swap in range(i):
            if yourlist[swap] > yourlist[swap + 1]:
                temp=yourlist[swap]
                yourlist[swap]=yourlist[swap + 1]
                yourlist[swap + 1]= temp
                count+= 1
    return yourlist, count

mylist = [20,30,40,90,50,60,70,80,100,110]
mylistx = [20,30,40,90,50,60,70,80,100,110]
sortedList, counter= bubbleshort(mylist)
sortList, count= bubble(mylistx)
print(sortedList,counter)
print(sortList,count)

此外，如果我将相同的列表传递给两个函数，则气泡函数生成零计数，但仍给出排序列表。那么有人能告诉我修改的目的到底是什么吗？通行证是一样的。他们可能是我对计数器的实施是错误的，这就是为什么我得到错误答案的原因。

Answer 1

这两个函数是否经过相同的遍数实际上取决于输入列表。

例如，像 [9,1,2,3,4,5,6,7,8] 这样的几乎排序的列表对于短冒泡函数只需要两次传递，而对于常规冒泡函数它总是需要 8 (n-1) 次传递。

短冒泡和冒泡排序的实现

Implementation of short bubble and bubble sort

sorting

algorithm

bubble-sort

python-3.x