写一个冒泡排序 python

### 冒泡排序算法的 Python 实现冒泡排序是一种简单的排序算法，其核心思想是通过多次比较和交换相邻元素的方式，将最大（或最小）的元素逐渐“冒泡”到数列的末尾[^1]。以下是冒泡排序算法的具体实现： ```python def bubble_sort(arr): """冒泡排序""" n = len(arr) for i in range(n - 1): # 外层循环控制从头走到尾的次数 count = 0 # 记录是否发生交换 for j in range(0, n - 1 - i): # 内层循环控制从头到尾的遍历 if arr[j] > arr[j + 1]: # 如果前一个元素大于后一个元素，则交换 arr[j], arr[j + 1] = arr[j + 1], arr[j] count += 1 if count == 0: # 如果没有发生交换，说明已经有序，提前退出 break ``` 在上述代码中，外层循环用于控制排序的轮数，而内层循环则负责逐一遍历数组并比较相邻元素。如果发现前一个元素比后一个元素大，则交换它们的位置[^3]。 #### 示例运行以下是一个完整的示例程序，展示如何使用上述函数对一个列表进行排序： ```python if __name__ == '__main__': list1 = [54, 26, 77, 17, 77, 31, 44, 55, 20] print('排序前:', list1) bubble_sort(list1) print('排序后:', list1) ``` 运行结果如下： ``` 排序前: [54, 26, 77, 17, 77, 31, 44, 55, 20] 排序后: [17, 20, 26, 31, 44, 54, 55, 77, 77] ``` 此外，还可以优化冒泡排序算法，通过引入标志位 `count` 来检测某一轮中是否发生了交换操作。如果没有发生任何交换，说明数组已经是有序状态，可以提前终止排序过程[^4]。 ### 时间复杂度分析冒泡排序的时间复杂度取决于输入数据的状态。最优情况下（即数组已完全有序），只需遍历一次数组即可完成排序，时间复杂度为 O(n)。最坏情况下（如数组逆序），需要进行 n*(n-1)/2 次比较和交换操作，时间复杂度为 O(n²)[^3]。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

下一篇 python字典如何修改key数据