冒泡排序

算法概述

1 .比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动态演示

代码示例

python版本

简单版本

# 某一趟遍历如果没有数据交换，则说明已经排好序了， # 因此不用再进行迭代了。用一个标记记录这个状态即可。 def good_bubble_sort1(ba_ary): print('sort1 arr:', ba_ary) n = len(ba_ary) for i in range(n): flag = True # 标记 for j in range(1, n - i): if ba_ary[j] < ba_ary[j - 1]: ba_ary[j], ba_ary[j - 1] = ba_ary[j - 1], ba_ary[j] flag = False print('第 j', j, '次', ba_ary) print('--------------------') print('第 i', i, '次', ba_ary) print('--------------------') # 某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了 if flag: break return ba_ary

运行结果

D:\python\python38\python.exe D:/lesson/python/操作文件/lesson1/com/gaoxiang/bubble_sort_demo.py sort arr: [9, 2, 8, 1, 3, 4, 10, 11, 12, 13] 第 j 1 次 [2, 9, 8, 1, 3, 4, 10, 11, 12, 13] 第 j 2 次 [2, 8, 9, 1, 3, 4, 10, 11, 12, 13] 第 j 3 次 [2, 8, 1, 9, 3, 4, 10, 11, 12, 13] 第 j 4 次 [2, 8, 1, 3, 9, 4, 10, 11, 12, 13] 第 j 5 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 6 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 7 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 8 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 9 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] -------------------- 第 i 0 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 2 次 [2, 1, 8, 3, 4, 9, 10, 11, 12, 13] 第 j 3 次 [2, 1, 3, 8, 4, 9, 10, 11, 12, 13] 第 j 4 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 5 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 6 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 7 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 8 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 1 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 4 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 5 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 6 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 7 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 4 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 5 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 6 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 4 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 5 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 4 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 4 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 5 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 6 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 7 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 8 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- -------------------- 第 i 9 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- Process finished with exit code 0

优化已经排好序了的操作的步骤

# 记录某次遍历时最后发生数据交换的位置， # 这个位置之后的数据显然已经有序，不用再排序了。 # 因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。 def good_bubble_sort2(ba_ary): print('sort2 arr:', ba_ary) n = len(ba_ary) k = n # k为循环的范围，初始值n for i in range(n): flag = True for j in range(1, k): # 只遍历到最后交换的位置即可 if ba_ary[j - 1] > ba_ary[j]: ba_ary[j - 1], ba_ary[j] = ba_ary[j], ba_ary[j - 1] k = j # 记录最后交换的位置 flag = False print('第 j', j, '次', ba_ary) print('--------------------') print('第 i', i, '次', ba_ary) print('--------------------') # 某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了 if flag: break return ba_ary

运行结果

D:\python\python38\python.exe D:/lesson/python/操作文件/lesson1/com/gaoxiang/bubble_sort_demo.py sort1 arr: [9, 2, 8, 1, 3, 4, 10, 11, 12, 13] 第 j 1 次 [2, 9, 8, 1, 3, 4, 10, 11, 12, 13] 第 j 2 次 [2, 8, 9, 1, 3, 4, 10, 11, 12, 13] 第 j 3 次 [2, 8, 1, 9, 3, 4, 10, 11, 12, 13] 第 j 4 次 [2, 8, 1, 3, 9, 4, 10, 11, 12, 13] 第 j 5 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 6 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 7 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 8 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 9 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] -------------------- 第 i 0 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 2 次 [2, 1, 8, 3, 4, 9, 10, 11, 12, 13] 第 j 3 次 [2, 1, 3, 8, 4, 9, 10, 11, 12, 13] 第 j 4 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 5 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 6 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 7 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 8 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 1 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 4 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 5 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 6 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 7 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 4 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 5 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 6 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- Process finished with exit code 0

优化最后排序位置

# 记录某次遍历时最后发生数据交换的位置， # 这个位置之后的数据显然已经有序，不用再排序了。 # 因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。 def good_bubble_sort2(ba_ary): n = len(ba_ary) k = n # k为循环的范围，初始值n for i in range(n): flag = True for j in range(1, k): # 只遍历到最后交换的位置即可 if ba_ary[j - 1] > ba_ary[j]: ba_ary[j - 1], ba_ary[j] = ba_ary[j], ba_ary[j - 1] k = j # 记录最后交换的位置 flag = False if flag: break return ba_ary

运行结果

D:\python\python38\python.exe D:/lesson/python/操作文件/lesson1/com/gaoxiang/bubble_sort_demo.py sort2 arr: [9, 2, 8, 1, 3, 4, 10, 11, 12, 13] 第 j 1 次 [2, 9, 8, 1, 3, 4, 10, 11, 12, 13] 第 j 2 次 [2, 8, 9, 1, 3, 4, 10, 11, 12, 13] 第 j 3 次 [2, 8, 1, 9, 3, 4, 10, 11, 12, 13] 第 j 4 次 [2, 8, 1, 3, 9, 4, 10, 11, 12, 13] 第 j 5 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 6 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 7 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 8 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 9 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] -------------------- 第 i 0 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [2, 8, 1, 3, 4, 9, 10, 11, 12, 13] 第 j 2 次 [2, 1, 8, 3, 4, 9, 10, 11, 12, 13] 第 j 3 次 [2, 1, 3, 8, 4, 9, 10, 11, 12, 13] 第 j 4 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 1 次 [2, 1, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 j 1 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] 第 j 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- 第 i 2 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- -------------------- 第 i 3 次 [1, 2, 3, 4, 8, 9, 10, 11, 12, 13] -------------------- Process finished with exit code 0