冒泡排序

主要思想：每轮依次 从前往后 比较相邻的两个元素，将两个元素中 较大的排在后面 ， 每一轮 可以将当前 未排序部分最大的置于最后。（每轮通过冒泡的方式将当前未排序部分最大的元素冒出）

提示：有每轮将最大的冒出这种方式冒泡，自然有每轮将最小的冒出到头部这种方式，这边所说的冒泡指的是前者（PPT里面说的也是前者啦）

1.1 简单演示

• 白色背景表示未排序部分
• 灰色背景表示已排序部分
• 淡蓝色表示正在进行对比交换的两个元素

• 初始状态

sort_base.png

• 初始状态有n=7个元素，所以 第一轮需要对n个元素进行n-1次交换尝试；

• 所谓交换尝试即如果左边元素大于右边元素，即执行交换 => 或

• 第一轮

sort.png

• 第一轮 结束就 有一个数已经排好序 了（它是数组中最大的元素，第一轮结束位于数组末尾），还剩n-1个元素未排序；

• 所以 第二轮需要对n-1个元素进行n-2次交换尝试；

• 第二轮

sort2.png

• 第二轮 结束 有两个数已经排好序 了，还剩n-2个元素未排序；

• 所以 第三轮需要对n-2个元素进行n-3次交换尝试

• 之后的若干轮操作相同，此处省略

1.2 实现分析

对于一个长度位n的待排序数组A，我们作如下分析

• 根据上面的演示分析，对于一个长度为n的数组，我们需要n-1轮对其排好序；

  => 在代码实现部分，轮数对应于第一个for循环：

  # 如果第一个for循环选择正向遍历，我们可以如下表示（我们后续讨论前者，后者不过是偏移不同而已）：
  for i in range(n - 1)    或   for i in range(1, n)
  
  # 如果第一个for循环选择反向遍历，我们可以如下表示（PPT中选择下面两种表示中的前面一种表示，我们后续讨论前者，后者不过是偏移不同而已）：
  for i in range(len(A) - 1, 0, -1) 或  for i in range(len(A) - 2, -1, -1)
  

• 对于第 i 轮，有m个数未排好序，对应于第二层for循环，至于具体如何表示，取决于第一层for循环如何表示（无论正向还是反向，核心就是：本轮如果有m个元素待排序，第二个for循环就应该有m - 1次交换尝试）：

  # 如果第一个for循环选择正向遍历，则两层循环的表示如下：
  for i in range(n - 1):
      for j in range(n - i - 1):
  
  # 如果第一个for循环选择反向遍历，则两层循环的表示如下（PPT中选择如下表示）：
  for i in range(len(A) - 1, 0, -1):
      for j in range(i):
  

• 因为我们的目标是 每轮将最大的数冒泡到末尾 ，所以对于循环内部，我们每次就是比较相邻两个数，如果左边的数大于右边的数，就交换两个数：

  if A[j] > A[j + 1]:
      A[j], A[j + 1] = A[j + 1], A[j]
  

1.3 实现

# 第一个for循环采用正向遍历的冒泡排序代码示例
def bubbleSort(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]


# 第一个for循环采用反向遍历的冒泡排序代码示例
def bubbleSort2(A):
    n = len(A)
    for i in range(n - 1, 0, -1):
        for j in range(i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]


if __name__ == '__main__':
    A = [5, 7, 1, 3, 6, 2, 4]
    bubbleSort(A)
    print(A, "= [1, 2, 3, 4, 5, 6, 7]")

    A = [5, 7, 1, 3, 6, 2, 4]
    bubbleSort2(A)
    print(A, "= [1, 2, 3, 4, 5, 6, 7]")