冒泡排序算法原理

发布时间：2023-06-28 14:15:56 所属栏目：教程来源：

导读：今天我们来详解冒泡排序算法，从原理到实现，然后再到算法分析三个部分完成对这个算法的剖析。

冒泡排序算法原理

所有的算法介绍都始于排序算法，所有的排序算法都会始于冒泡排序。排序问题是一个非常古老的问

今天我们来详解冒泡排序算法，从原理到实现，然后再到算法分析三个部分完成对这个算法的剖析。

冒泡排序算法原理

所有的算法介绍都始于排序算法，所有的排序算法都会始于冒泡排序。排序问题是一个非常古老的问题，从算法出生就被研究到现在。当然主要是排序的规模再不断扩大，从一开始的几百到几千个数排序，到现在对几百亿个数甚至几千亿数进行排序，这里面用到的技术和算法远远超过我们的想象。当然，千里之行，始于足下，今天我们以这个冒泡算法为例，正式进入算法的世界。

排序问题：给定一列数据，对它们进行排序，并按照从小到大 (或者从大到小) 的顺序输出；

输入: [, , , , , , , ]
输出: [, , , , , , , ]
我们来用冒泡排序算法来解决一下这个问题，在开始动手写代码之前先来看下冒泡排序的原理：

冒泡排序的思想比较简单，对于需要从小到大排列的数组，我们采用这样的方式：从第一个位置开始，两两比较相邻元素的大小（第一个位置和第二个位置），如果前者比后者大，那么交换两者的位置；接下来比较下一个相邻位置（第二个位置和第三个位置）元素的大小，然后将大的值放到后面，这样一直比较到最后一个位置，此时数组中的最大值就会落到最后一个位置上，这时第一轮比较就结束了。

接着开始第二轮比较，同样是从第一个位置开始，两两相邻比较，将较大者交换到后面位置，但这次我们比较到倒数第二个位置即停止。此时倒数第二个位置的元素就是除最后一个元素外的最大值。

冒泡排序算法分析

以此类推，对于 n 个元素的排序，在第 n-1 轮迭代后，我们的排序工作就结束了，此时的数组正是从小到大依次排列好。下面我们用一幅图对冒泡排序算法进行说明，如下：

冒泡排序第一轮迭代

在第一轮迭代完成后，全局的最大值便落到了最后位置。接下来的第二轮迭代中，我们就不会再比较这个位置，而是相邻比较到倒数第二个位置结束；接下来第三轮迭代是比较到倒数第三个位置结束；以此类推，直到最后一轮迭代只剩下一个元素即可，此时得到的排列顺序正是从小到大的有序排序。

冒泡排序的思想就是这样：通过一轮相邻元素的比较，将最大值找到并交换到最后的位置，第二轮找到第二大的值，放到倒数第二个位置，直到最后一轮迭代，找到第二小的值，放到第二个位置上，最小值此时就在第一个位置上。接下来我们就开始完成该算法的 Python 编程。

冒泡排序算法 Python 实现

基础的冒泡排序实现代码如下：

# 代码位置：sort_algorithms.py
def bubble_sort(nums):
"""
冒泡排序算法
输入：nums，无序列表
执行完后该nums值会变成有序列表
"""
for i in range(len(nums) - ):
for j in range(, len(nums) - i - ):
# 如果当前元素比下一个元素大，则交换两个元素，保证左边的比右边的元素要小
if nums[j] > nums[j + ]:
# 交换相邻元素
nums[j], nums[j + ] = nums[j + ], nums[j]
我们简单写个代码测试下这个函数：

# 冒泡排序算法
from sort_algorithms import bubble_sort
if __name__ == '__main__':
nums = [, , , , , , , ]
bubble_sort(nums)
print('排序后的nums:{}'.format(nums))
执行后结果如下：

排序后的nums:[2, 3, 6, 7, 8, 10, 11, 12]
这里的实现非常简单，注意两个 for 循环的次数即可，然后便是相邻数据比较，满足条件即交换数据。接下来我们要分析这种算法的复杂度。

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!