python - 解释冒泡排序算法？

Question

我正在尝试了解有关算法的更多信息，并且正在研究冒泡排序算法。我在 github 上找到了它的脚本，但我真的无法理解它。我是 python 的新手，所以有人可以向我解释这个脚本中发生了什么。

from __future__ import print_function

def bubble_sort(arr):
  n = len(arr)
  # Traverse through all array elements
  for i in range(n):
    # Last i elements are already in place
      for j in range(0, n-i-1):
        # traverse the array from 0 to n-i-1
        # Swap if the element found is greater
        # than the next element
        if arr[j] > arr[j+1] :
              arr[j], arr[j+1] = arr[j+1], arr[j]
  return arr

if __name__ == '__main__':
    try:
        raw_input          # Python 2
    except NameError:
        raw_input = input  # Python 3
    user_input = raw_input('Enter numbers separated by a comma:').strip()
    unsorted = [int(item) for item in user_input.split(',')]
    print(*bubble_sort(unsorted), sep=',')

Answer 1

将数组可视化为垂直的数字列表，第一个元素(索引 0)在底部，最后一个元素(索引 n-1)在顶部。冒泡排序的想法是数字“冒泡”到顶部，进入它们所属的位置。

例如，[2,3,1] 会先查看 2 和 3，然后什么都不做，因为它们已经排好序了。然后它会查看 3 和 1，交换它们，因为 3>1 并得到 [2,1,3]。然后我们重复查看 2 和 1，交换它们，因为 2>1 得到 [1,2,3]，这是有序的。

想法是“3”然后“2”冒泡到正确的位置。

请注意，在 3 冒泡之后，我们不必比较 2 和 3，因为我们知道最后一个元素已经高于它之前的所有元素。通常，在冒泡排序的 i 次迭代之后，不需要比较最后的 i 个元素。