气泡在Python中排序复杂性

Question

im IM在编程和IM现在学习Pyhon的初学者。我在互联网上看到了许多泡沫，使用两个循环。我理解了，但是我想在周期时写自己的使用。我终于写了它，它起作用了。我的代码很复杂，可能很糟糕。有人说我，如果我更改它会"更快"。例如，当我输入6个未分类的数字时，复杂性是25。但是，当我输入6个排序数字（例如1,2,3,4,5,6）时，复杂性仍然25。， 不？我添加了其他条件，但没有工作。

lst=[]
number=""
while number!="k":
    number=input("Enter a nubmer (to end press K): ")
    if number!="k":
        number=int(number)
        lst.append(number)
print("Numbers before: ",lst,)
repetition=len(lst)-1
index=0
complexity=0
while repetition>0:
    repetition=repetition-1
    while index<=len(lst)-2:
        complexity=complexity+1
        if lst[index]>lst[index+1]:
              hlp=lst[index]
              lst[index]=lst[index+1]
              lst[index+1]=hlp
        index=index+1        
    index=0
print("Numbers after: ",lst,)
print("Complexity:",complexity,)

您能告诉我在哪里应该更改它或直接如何更改它？谢谢。

Answer 1

bubblesort算法复杂性在最坏的情况下始终是 O(N^2)，无论选择用于实施它的编程语言。

Answer 2

气泡排序始终是n^2运行时，无论初始列表的顺序如何，因为它始终贯穿每个元素对。无论您要排序列表的顺序如何，您的代码的复杂性都应相同，因此从这个意义上讲，您的复杂性输出是正确的。如果需要更好的复杂性，则需要其他排序算法。