Python冒泡排序的原理和代码

Python冒泡排序的原理和代码

冒泡排序是一种简单的排序算法,它的原理如下:

  1. 从待排序的列表的第一个元素开始,依次比较相邻的元素。
  2. 如果前一个元素大于后一个元素,则交换这两个元素的位置。
  3. 继续向后遍历,对每一对相邻的元素进行比较和交换操作,直到遍历到列表的最后一个元素。
  4. 上述操作完成一轮遍历后,列表中最大的元素就会被移到最后。
  5. 重复执行上述步骤,每次遍历的元素范围逐渐减小,直到整个列表有序为止。

通过不断比较相邻元素并交换位置,冒泡排序将每一轮遍历中最大的元素“浮”到了列表的末尾。经过多轮遍历,列表中的元素按照从小到大(或从大到小)的顺序逐渐排列。

冒泡排序的时间复杂度为O(n^2),其中n是待排序列表的长度。由于需要进行多次遍历,即使在最好的情况下,也需要进行n-1次比较和交换操作。因此,冒泡排序对于大型数据集并不是一个高效的排序算法。但是,冒泡排序在实现简单、代码易于理解的同时,对于小型数据集或部分有序的数据集,仍然是一个有效的选择。

def bubble_sort(arr):
n = len(arr)

# 外层循环控制比较的轮数
for i in range(n - 1):

    # 内层循环进行相邻元素比较和交换
    for j in range(n - 1 - i):

        # 如果前一个元素大于后一个元素,则交换它们的位置
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]

测试代码

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(“排序后的数组:”, arr)

输出结果:

排序后的数组: [11, 12, 22, 25, 34, 64, 90]

以上代码中,bubble_sort函数接受一个列表作为参数,并对其进行冒泡排序。外层循环控制比较的轮数,而内层循环则进行相邻元素的比较和交换。如果前一个元素大于后一个元素,就使用Python的交换语法将它们的位置交换。最终,排序完成后,原始的列表会被修改为按照从小到大的顺序排列的列表。

评论已关闭。