冒泡排序是一种简单的排序算法,其原理是通过交换相邻两个元素的位置,将最大的元素逐渐"冒泡"到最后面。具体来说,该算法从列表的开头开始,依次比较相邻两个元素的大小,如果前一个元素比后一个元素大,则交换它们的位置。这样一趟排序后,最大的元素就会被排在列表的最后面。然后再从列表开头开始进行下一趟排序,但此时最后面的元素已经是有序的,不再参与排序。
下面是冒泡排序的实现代码(以从小到大排序为例):
def bubble_sort(arr):
n = len(arr)
for i in range(n):
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
在上述代码中,arr是要进行排序的列表,n是列表的长度。外层循环控制排序的趟数,内层循环控制每一趟的比较和交换操作。每一趟排序会将当前列表中最大的元素排到最后面,因此内层循环的范围是n - i - 1。如果相邻的两个元素大小关系不正确,就交换它们的位置。最后返回排序后的列表。
冒泡排序的时间复杂度是$O(n^2)$,空间复杂度是$O(1)$。它虽然简单,但在实际应用中由于时间复杂度较高,因此很少被使用。
相关文章
关注千锋学习站小程序
随时随地免费学习课程
扫一扫快速进入
千锋移动端页面
扫码匿名提建议
直达CEO信箱