冒泡排序的原理是:从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。 以从小到大排序为例,第一轮比较后,所有数中最大的那个数就会浮到最右边;第二轮比较后,所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较,最后实现从小到大排序。
代码如下
# 定义一个列表,用于存放需要排序的数字
arr = [64, 34, 25, 12, 22, 11, 90]
# 定义冒泡排序的函数,这里不需要参数,因为列表是可变的
def bubble_sort():
# 外层循环控制排序的总轮数,为列表长度
for i in range(len(arr)):
# 内层循环控制每轮中比较的次数,
#不用跟自己比较和每一次会有一个最大的数”沉底“,所以是len(arr)-1-i;
for j in range(len(arr) - i - 1):
# 如果当前元素大于下一个元素,说明顺序错误
if arr[j] > arr[j + 1]:
# 交换当前元素和下一个元素的位置
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# 调用冒泡排序函数,对arr列表进行排序
bubble_sort()
# 打印排序后的列表
print(arr)
可以对其进行优化:
- 设置标志位:如果在一轮遍历中没有进行任何交换,说明列表已经是有序的,可以提前结束排序。
- 记录最后一次交换的位置:每轮冒泡排序中,最大的元素会被放到它应该在的位置,这意味着在它之后的元素已经是有序的,下一轮可以不用再次检查。
# 定义一个列表,用于存放需要排序的数字
arr = [64, 34, 25, 12, 22, 11, 90]
# 定义优化后的冒泡排序函数
def optimized_bubble_sort(arr):
n = len(arr)
# 设置标志位,用于检测是否有交换发生
swapped = True
while swapped:
swapped = False
# 记录最后一次交换的位置,下一轮可以不用再次检查这个位置之后的元素
last_swap_index = 0
# 内层循环控制每轮中比较的次数,每轮减少1
for i in range(1, n):
if arr[i - 1] > arr[i]:
# 交换当前元素和下一个元素的位置
arr[i - 1], arr[i] = arr[i], arr[i - 1]
# 更新最后一次交换的位置
last_swap_index = i
# 有交换发生,标志位设为True
swapped = True
# 减少下一轮的比较次数,因为last_swap_index之后的元素已经是有序的
n = last_swap_index
# 调用优化后的冒泡排序函数,对arr列表进行排序
optimized_bubble_sort(arr)
# 打印排序后的列表
print(arr)
运行结果:
[11, 12, 25, 34, 64, 90, 212]
Comments NOTHING