算法009_冒泡排序

冒泡排序（Bubble Sort）

• 列表每两个相邻的数，如果前面比后面大，则交换这两个数
• 一趟排序完成后，则无序区减少一个数，有序区增加一个数
• 代码关键点：趟、无序区范围
  • 第 0 趟的时候无序区没有数
  • 第 n - 1 趟的时候有一个数
  • 第 i 趟的时候，无序的长度是 n - i - 1
  • 最底下的是无序区，最上面的是有序区。无序区慢慢减少变的只剩一个，有序区慢慢增加到 n - 1
• 时间复杂度：

图解冒泡排序
箭头从数值 7 开始，第一趟比较 7 和 5，7 > 5 进行交换
接着 7 和 4 相比，7 > 4，继续交换
接着 7 和 6 相比，7 > 6，继续交换

冒泡排序交换过程01
接着 7 和 3 比，进行交换
接着 7 和 8 比，7 < 8，不交换数字，但是箭头一直得向上
接着 8 和 2 比，进行交换 冒泡排序交换过程02

接着 8 和 9 比，不交换，箭头上移
接着 9 和 1比，交换，此时最大的数 9 已经在最上面了
这就是冒泡排序的一趟。注意最后只会指到倒数第二个元素（从下往上的倒数第二个元素），因为它永远都要和它后面的数进行比较。
在这一趟的过程当中，有一个最大的数上去了

冒泡排序交换过程03

当一趟排序完成之后，箭头上面的就是有序区，箭头下面就是无序区

然后接着会对无序区进行排序
整个排序算法需要进行 n - 1 趟，因为最后剩下来的就是最小的或者最大的数

代码

import random


def bubble_sort(target_list):
    for i in range(len(target_list) - 1):  # 第i趟
        for j in range(len(target_list) - i - 1): # 箭头指向
            if target_list[j] > target_list[j + 1]:
                # 箭头指的数大于箭头指的后一个数
                target_list[j], target_list[j + 1] = target_list[j + 1], target_list[j]


test_list = [random.randint(0, 100) for i in range(10)]
print("排序之前: ", test_list)
bubble_sort(test_list)
print("排序之后: ", test_list)

"""
排序之前:  [95, 20, 68, 74, 42, 85, 40, 81, 85, 92]
排序之后:  [20, 40, 42, 68, 74, 81, 85, 85, 92, 95]
"""

改进版
冒泡排序改进：如果在排序的过程当中，没有发生任何数据的交换，就可以认为这个列表已经被排好序了，就可以不用排了
在排序之前添加标志位 exchange = False，如果发生了排序就设置 exchange = True。如果一趟排序结束之后，exchange 为 False，说明没有交互，就可以直接跳出循环，结束排序

def bubble_sort(target_list):
    for i in range(len(target_list) - 1):  # 第i趟
        exchange = False
        for j in range(len(target_list) - i - 1): # 箭头指向
            if target_list[j] > target_list[j + 1]:
                # 箭头指的数大于箭头指的后一个数
                target_list[j], target_list[j + 1] = target_list[j + 1], target_list[j]
                exchange = True
        if exchange is False:
            return
        print("交换之后的数组: ", target_list)


test_list = [9, 1, 2, 3, 4, 5, 6, 7, 8]
print("原始数组: ", test_list)
bubble_sort(test_list)

"""
原始数组:  [9, 1, 2, 3, 4, 5, 6, 7, 8]
交换之后的数组:  [1, 2, 3, 4, 5, 6, 7, 8, 9]
"""

如果传入的数据是已经按照要求排好的，进阶版本就只需要排一趟，基础版本需要 n - 1 趟