这个冒泡排序逻辑是否正确

Question

我在 youtube 上看到了一些关于列表排序技术、冒泡排序的视频，他们使用的代码是

list1 = [4, 8, 5, 3, 1]

for i in range(len(list1)-1, 0, -1):
    for j in range(i):
        if list1[j] > list1[j+1]:
            t = list1[j]
            list1[j] = list1[j+1]
            list1[j+1] = t
print(list1)

在没有 python 的情况下我自己对不同的列表进行排序后，我发现了一个模式，并对代码进行了轻微的安排，我得到了相同的输出。

list1 = [4, 8, 5, 3, 1]

for i in range(1,len(list1)):
    for j in range(len(list1)-1):
        if list1[j] > list1[j+1]:
            t = list1[j]
            list1[j] = list1[j+1]
            list1[j+1] = t

print(list1)

但在这里，我只想知道逻辑是否相同，方法也是冒泡排序，因为将来让我做冒泡排序时，我不想这样做，结果很尴尬:p

提前致谢:D

Answer 1

算法是冒泡排序，但有不必要的比较。您通过对所有 n 个元素迭代 n 次对其进行排序。但是第一次后保证最高值在最后一个位置，所以下一步只需要遍历前n-1个元素，以此类推。在你的算法中，你只是继续到最后。这并没有错，但效率不高。但是它不会改变 O(n^2) 的时间复杂度。

编辑：回复一些评论：是的，一般来说你不使用冒泡排序来提高效率。但有一种情况，它表现得相当好（通过优化，当有一个迭代没有变化时你就停止了），那就是如果你有一个几乎排序的列表。

这个冒泡排序逻辑是否正确

Is this Bubble sort logic correct

python

python-3.x

list

bubble-sort