不再慌乱！Python冒泡算法帮你快速整理数据
冒泡算法大揭秘：教你用Python轻松排序数据
冒泡排序是一种简单但低效的排序算法,它通过多次遍历要排序的元素,依次比较相邻的两个元素,如果它们的顺序不正确就交换它们,直到没有再需要交换的元素为止.冒泡排序的特点是每一轮排序都会将当前未排序部分中最大（或最小）的元素移动到正确的位置.
下面是冒泡排序的示例过程：
- 假设我们有一个包含6个元素的数组 [5, 3, 8, 2, 1, 4] 进行升序排序. 第一轮排序： • 比较第1和第2个元素： 3 < 5,保持原序 • 比较第2和第3个元素： 3 < 8,保持原序 • 比较第3和第4个元素： 2 < 8,保持原序 • 比较第4和第5个元素： 1 < 8,保持原序 • 比较第5和第6个元素： 4 < 8,保持原序 数组变为 [3, 5, 2, 1, 4, 8] 第二轮排序： • 比较第1和第2个元素： 3 < 5,保持原序 • 比较第2和第3个元素： 2 < 5,保持原序 • 比较第3和第4个元素： 1 < 5,保持原序 • 比较第4和第5个元素： 4 < 5,保持原序 数组变为 [3, 2, 1, 4, 5, 8] 第三轮排序： • 比较第1和第2个元素： 2 < 3,保持原序 • 比较第2和第3个元素： 1 < 3,保持原序 • 比较第3和第4个元素： 3 < 4,保持原序 数组变为 [2, 1, 3, 4, 5, 8] 重复这个过程直到整个数组排序完成.
def bubble_sort(arr): n = len(arr) for i in range(n): # 标记是否发生交换 swapped = False for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True # 如果本轮没有发生交换,说明数组已经有序 if not swapped: break print(f"第{i+1}轮排序: {arr}") # 初始数组 arr = [5, 3, 8, 2, 1, 4] print("初始数组:", arr) bubble_sort(arr) print("已排序数组:", arr) 输出：
初始数组: [5, 3, 8, 2, 1, 4] 第1轮排序: [3, 5, 2, 1, 4, 8] 第2轮排序: [3, 2, 5, 1, 4, 8] 第3轮排序: [3, 2, 1, 5, 4, 8] 第4轮排序: [3, 2, 1, 4, 5, 8] 第5轮排序: [2, 3, 1, 4, 5, 8] 第6轮排序: [2, 1, 3, 4, 5, 8] 第7轮排序: [2, 1, 3, 4, 5, 8] 第8轮排序: [1, 2, 3, 4, 5, 8] 第9轮排序: [1, 2, 3, 4, 5, 8] 已排序数组: [1, 2, 3, 4, 5, 8] 冒泡排序的基本思路有那些：
通过多次遍历待排序的元素列表,比较相邻的元素并根据需要交换它们的位置,直到整个列表排好序为止.除了这种最基本的实现方式外,还有一些优化和变种方法可以改进冒泡排序的性能：
标记交换：如果在某一轮遍历中没有进行过任何元素位置的交换,说明整个数组已经有序,可以提前结束排序过程.
改进的冒泡排序：通常情况下,冒泡排序会将每轮遍历时剩余未排序部分的所有元素都进行比较.但实际上,每一轮排序其实只需比较到未排序部分中最后一次发生交换的位置即可,因为该位置之后的元素已经有序.
鸡尾酒排序（双向冒泡排序）： 鸡尾酒排序是冒泡排序的一种变体,它来回地在待排序元素中进行冒泡操作.这样可以在某些情况下更快地找到最大和最小值,并将它们放到正确的位置上.
逆序对的利用： 如果待排序的元素中包含逆序对数量的统计信息,可以利用逆序对的数量判断数组是否已经有序,从而减少不必要的比较.
冒泡排序的时间复杂度为O(n^2),其中n是要排序元素的数量.虽然冒泡排序简单易懂,但对于大型数据集并不高效,因此在实际应用中很少使用.
感谢大家的关注和支持!想了解更多Python编程精彩知识内容,请关注我的 微信公众号:python小胡子,有最新最前沿的的python知识和人工智能AI与大家共享,同时,如果你觉得这篇文章对你有帮助,不妨点个赞,并点击关注.动动你发财的手,万分感谢!!!
