冒泡排序：
冒泡排序无疑是最为出名的排序算法之一，从序列的一端开始往另一端冒泡，依次比较相邻的两个数的大小。重复性的工作直到没有可以交换的两个元素，说明数列已经排序完成。冒泡算法的时间复杂度为O(n2)。
image.png
算法思想
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 每次循环固定一个数，比较的次数依次减1
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
经典排序算法学习笔记_冒泡算法
冒泡排序
一文看懂冒泡排序算法
吴大佬-必须好好学习
图片发自简书App
通过一个简单的例子来进行说明，冒泡排序算法的具体过程，现在有一个列表list = [8, 2, 5, 9, 7]，如何通过冒泡算法实现排序：
1.jpg
首先比较第一个数字和第二个数字，发现8比2大，则8位置不动，整体还是[8,2,5,9,7]，此时指针右移一格
2.jpg
比较第二个数和第三个数的大小，发现2比5小，则交换它们的位置，5放到2的前面，变成[8,5,2,9,7]，指针右移一格
3.jpg
比较第三个数和第四个数的大小，发现2比9小，交换位置，变成[8,5,9,2,7]，指针右移一格。
4.jpg
比较第四个数和第五个的大小，发现2比7小，交换位置，变成[8,5,9,7,2]，指针右移发现已经到底。
第一轮的冒泡结束，第二轮开始
5.jpg
比较第一个和第二个数，8比5大，保持不变，指针右移
6.jpg
比较第二个和第三个数，发现5比9小，交换位置，变成[8,9,5,7,2]，只有指针右移。
7.jpg
比较第三个和第四个数，发现5也比7小，交换位置，变成[8,9,7,5,2]，指针右移；再比较第四个和第五个数字，5比2大，保持不变。
8.jpg
经过两轮的冒泡排序，变成了[8,9,7,5,2]的效果，经过多次循环的过程最终一定会变成[9,8,7,5,2]
Python代码实现
list1 = [1,7,3,5,2]
length = len(list1)
for i in range(length-1)：# 外层控制总的循环次数，需要length-1；最后一个数自己无需比较，写成length也无妨，一般写成length-1。同时i表示本轮结束后有i个数已经排好序
for j in range(length-1-i): # 内层循环控制每轮循环中比较的次数，但i轮之后排好序的i数无需进行排列。
if list1[j] > list1[j+1]:
list1[j], list1[j+1] = list1[j+1], list1[j]
print(list1)
def bubble_sort(nums):
for i in range(0, len(nums) - 1): # 设置冒泡排序进行的次数
for j in range(0, len(nums) - 1 - i): # j为列表下标
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
if __name__ == "__main__":
lists = [1,9,3,5,2,8,4,6,10,7]
bubble_sort(lists)
print(lists)
# print(bubble_sort([1,9,3,5,2,8,4,6,10,7]))
def bubble(list1):
length = len(list1)
for i in range(length - 1):
print(f"i = {i}")
for j in range(length - 1 - i):
print(f"j = {j}", end=" ")
if list1[j] > list1[j+1]:
print("swap", end=" ")
list1[j], list1[j+1] = list1[j+1], list1[j]
print(list1)
-
i代表循环的总轮数为列表的长度len(list1)；外层 -
j代表每次循环中比较的次数- 减1：最后一个数不需要比较
- 减i：i轮之后无需再比较已经排好序的i个数
优化
def bubble(list1):
length = len(list1)
for i in range(length - 1):
flag = False # 设置一个标志位
for j in range(length - 1 - i):
if list1[j] > list1[j + 1]:
list1[j], list1[j+1] = list1[j+1], list1[j]
flag = True # 如果两个元素之间交换了位置，标志位设为True
if flag == False: # 等价于if not flag
break # 如果经历一个循环之后还是False，结束循环
return list1
image.png
