练习：冒泡排序法

冒泡排序法：是在每一轮排序结束之后都有一个体积最大的气泡冒出来，这也正是冒泡排序法名字的由来。

(1)从集合第一个元素开始，每两个相邻的元素进行大小比较，令数值较大的元素向后移动，即交换两个元素的位置，不断对比直至数组的末尾。经过第一趟对比，找到整个集合中最大的元素，并将其移动到集合最后一个位置。
(2)继续进行第二趟排序，仍然从集合的第一个元素出发，相邻两元素对比，让较大者向后移动，不断对比至集合中倒数第二个元素为止。此时可以找到整个集合中第二大的元素，并使其处于集合的倒数第二位。
(3)每趟结束之后都会有一个元素找到自己最终在集合中的位置，不断从第一个元素开始进行 n-1 趟上述过程，即可完成所有元素的排序，实现将集合从小到大排序。

把集合中每一个数想象成在水中纵向放置、体积大小不一的气泡，数值越大气泡的体积越大。

实现如下：

1、nums 变量：表示待排序数组名，为list类型
2、flag 变量：每趟排序开始时为0，一旦发生元素交换变为1。如果一趟对比结束后之后 flag 值为0，说明没有发生元素交换，已经排序完毕，可以终止排序，跳出循环。

 1 def Bubblesort(nums):
 2     for i in range(len(nums)-1):
 3         flag=0
 4         for j in range(len(nums)-1-i):
 5             if(nums[j]>nums[j+1]):  # 将较大的往后移
 6                 temp=nums[j+1]
 7                 nums[j+1]=nums[j]
 8                 nums[j]=temp
 9                 flag=1
10         if flag==0:break
11     return nums

时间复杂度：最坏的情况下，要进行n-1趟排序，为n的平方
空间复杂度：为1

2023-9-10笔记