冒泡排序是一种简单的排序算法,它通过重复地交换相邻的元素,直到整个序列按照升序或降序排列。它的工作原理如下:
- 比较相邻的两个元素。如果前一个元素大于后一个元素,就交换它们的位置。
- 对整个序列重复步骤1,直到没有任何一对相邻元素需要交换,也就是说序列已经按照升序排列完成。
具体过程如下:
- 从第一个元素开始,比较相邻的两个元素。如果第一个元素大于第二个元素,就交换它们的位置。
- 对剩余的元素重复步骤1,直到最后一个元素。
- 重复步骤1-2,直到整个序列按照升序排列完成。
附冒泡排序代码实现：
#时间复杂度：O(n**2) def bubble_sort(li): for i in range(len(li)-1): #第i趟 flag = False #巧妙思路 判断第i趟过去之后是否有数的交换 减少不必要的循环 for j in range(len(li)-i-1): #箭头指第几个数 if li[j]>li[j+1]: li[j],li[j+1]=li[j+1],li[j] flag = True #如果进行了交换 则标志改变 print(li) if not flag: #如果白白走了一趟 说明已经排好 没必要继续循环下去 可以直接停止 return #停止循环 减低时间复杂度 li=[3,2,5,6,8,7,4,9,1] bubble_sort(li)
冒泡排序的时间复杂度为O(n^2),因为它需要进行n-1轮比较和交换操作。虽然它是一种简单的排序算法,但在某些情况下效率较低,因此在实际应用中通常会使用更高效的排序算法,如快速排序、归并排序等。
