Python排序算法-冒泡排序

上一节：选择排序，是选出一个元素与后面的全部元素逐个比较，选出一个最大或最小的元素。

而冒泡排序，则略有不同，他是将相邻的两个元素两两相互比较，其中较大（较小）的元素以互换的形式向后移动。

• 实现方式

两两相互比较，即将j与j+1相互比较，也是通过两层循环遍历的方式实现：

• 列表的长度为n，即列表所有元素的表示范围为：[0,n-1]
• 外层循环从列表尾部[n-1]先开始，最大的元素位置在最后一个；到第2个结束，即列表的表示范围[n-1,1]，这是因为前面元素全部比较完毕，最后一个元素[0]自然是最小的，无须再比较。因此循环的写法为：for i in range(n-1,0,-1)
• 内层循环从0开始，到倒数第2个结束，即内层循环的表示范围[0,n-1-1]，因为后面比较的方式是nums[j+1]，这样就可以比较到最后一个元素。因此循环的写法为for j in range(i)
• 同时，可以在外层循环内部定义一个标志变量flag，如果列表是有序的，即在内层循环遍历是没有出现两两互换，说明已经是有序列表，可以跳出循环，终止排序。

# 冒泡排序
#
def bubble_sort(nums:list[int]):
    n=len(nums)
    # 外层循环从列表尾部先开始，目的：为内层循环设置最大的范围；
    # 注意外层循环范围为：[n-1,1]，前面元素全部比较完毕，最后一个元素[0]自然是最小的，无须再比较
    for i in range(n-1,0,-1):
        # 定义一个标志变量，如果后面元素是有序的（没有元素交换操作），无须排序，直接终止
        flag = True
        # 内层循环范围：[0,n-1-1]，因为后面比较的方式是nums[j+1]，这样就可以比较到最后一个元素
        for j in range(i):
            if nums[j]>nums[j+1]:
                nums[j],nums[j+1]=nums[j+1],nums[j]
                flag=False
        if flag:
            break

if __name__=="__main__":
    nums = [62, 65, 51, 15, 30, 63, 37, 8, 55, 70, 13, 84, 46, 44, 86, 11, 91, 10, 47, 3, 96, 9, 36, 54, 24, 55, 72,
            29, 45]
    bubble_sort(nums)
    print(nums)