通过交换相邻元素对列表进行排序

Question

通过反复试验，我已经找到了解决方案，但我不明白它为什么有效。

n=input()
f=n.split(' ')
count = 0

while count <  ( len(f) * (len(f)-2) ):
    
    for z in range(1, len(f)):
       
        if int(f[z]) > int(f[z-1]):
            f[z], f[z-1] = f[z-1], f[z]
       
        if int(f[z]) < int(f[z-1]):
            count +=1
            
print (f)

所以我开始在第5行只使用

while count < len(f)

，很快就明白为什么它不起作用，我尝试了

len(f)

的不同倍数，很快得出结论

len(f) * (len(f)-2)

是我需要检查的标准，它确实适用于其上方的所有值，例如

len(f) **2

我只是一个初学者，不明白它只适用于

len(f) * (len(f)-2)

及以上。 有人可以尽可能简单地解释一下吗，谢谢。

Answer 1

对于上下文，您可能希望回顾一下大 O 表示法：可以在here找到一个很好的起点（尝试维基百科以获得更正式的解释）。我将解释原因，但不需要了解此符号。

您的代码是冒泡排序的实现，其最坏情况时间复杂度为n平方（大O表示法中的O(n^2)），其中n是列表的长度。这意味着在最坏的情况下，完成所需的时间与列表长度的平方成正比。最好通过查看反向排序列表的最坏情况来解释这一点。

以下grepper答案实现了冒泡排序：

# Credit to: https://www.grepper.com/profile/wissam-fawaz
def bubble_sort(array):
    isSorted = False
    passes = 0
    length = len(array)
    while not isSorted:
        isSorted = True
        # perform a pass through the array
        # excluding already sorted positions
        for i in range(length-1-passes):
            if array[i] > array[i+1]:
                swap(i, i+1, array)
                # array is not sorted yet
                isSorted = False
        passes += 1
    return array

def swap(i, j, array):
    # Swap values at indexes i and j
    array[i], array[j] = array[j], array[i]

该算法将循环遍历反向排序列表，在每个点将最小的数字打乱到底部。例如，对于列表 [4, 3, 2, 1]：

迭代 1：
[3,2,1,4]

迭代 2：
[2,1,3,4]

迭代 3：
[1,2,3,4]

迭代 4（检查）：
[1,2,3,4]

如您所见，我们已经执行了

while

循环 4 次，并且内部

for

循环在

while

循环中的每个循环中迭代了列表中的每个元素，导致最坏情况时间n 平方的复杂度。

您的算法的

count

会计算进行的交换次数。因此，在最坏的情况下，这个数字将与列表长度的平方成正比。