python冒泡排序从小到大_大一python笔记

激活谷笔记 • 2025-05-17 21:32 • 阅读 99

冒泡排序是一种简单的排序算法，其基本思想是通过重复遍历列表，比较相邻素并交换位置，使得每一轮遍历后最大的素被移动到列表的末尾。以下是冒泡排序的优化方法：

1. 添加标志位：

在每一轮遍历中，设置一个标志位来检查是否发生了交换。如果在一次遍历中没有发生任何交换，说明列表已经排序完成，可以提前结束排序过程。

 def optimized_bubble_sort（arr）: n = len（arr） for i in range（n - 1）: swapped = False for j in range（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 return arr[1:] 返回排序后的列表，去掉最后一个素

2. 选择排序：

在选择排序中，交换发生在外部循环，可以优化为从大到小排序，这样可以在一次遍历中确定最大素的位置，减少不必要的比较。

 def selection_sort_descending（arr）: n = len（arr） for i in range（n - 1）: max_index = i for j in range（i + 1, n）: if arr[j] > arr[max_index]: max_index = j arr[i], arr[max_index] = arr[max_index], arr[i] return arr

3. 减少比较次数：

在每一轮遍历中，由于最大的素已经被移动到末尾，所以下一轮遍历可以忽略已经排序好的素，即内层循环的结束条件可以改为`j < n - i - 1`。

 def optimized_bubble_sort_v2（arr）: n = len（arr） for i in range（n - 1）: for j in range（n - i - 1）: if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr[1:] 返回排序后的列表，去掉最后一个素

以上是冒泡排序的一些优化方法，通过这些优化，可以提高冒泡排序的性能，尤其是在部分或完全排序的列表中。需要注意的是，这些优化方法并不会改变冒泡排序的时间复杂度，它仍然是最坏情况下为O（n^2）的排序算法。

python冒泡排序从小到大_大一python笔记

相关推荐