冒泡排序

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

1. 冒泡排序算法原理

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

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

输入: [8, 7, 12, 3, 2, 11, 10, 6]
输出: [2, 3, 6, 7, 8, 10, 11, 12]

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

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

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

1. 冒泡排序算法分析

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

图片描述

在第一轮迭代完成后,全局的最大值便落到了最后位置。接下来的第二轮迭代中,我们就不会再比较这个位置,而是相邻比较到倒数第二个位置结束;接下来第三轮迭代是比较到倒数第三个位置结束;以此类推,直到最后一轮迭代只剩下一个元素即可,此时得到的排列顺序正是从小到大的有序排序。下面给出第二轮迭代示意图,其余迭代过程依次类推:

图片描述

在经过 n-1 轮迭代后,最后得到的结果就是我们想要的从小到大的排序顺序:

2,3,6,7,8,10,11,12

如果你还是不明白冒泡排序的原理的话,可以看下面的动态图:

图片描述

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

3. 冒泡排序算法 Python 实现

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

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

我们简单写个代码测试下这个函数:

# 冒泡排序算法
from sort_algorithms import bubble_sort
if __name__ == '__main__':
 nums = [8, 7, 12, 3, 2, 11, 10, 6]
 bubble_sort(nums)
 print('排序后的nums:{}'.format(nums))

执行后结果如下:

排序后的nums:[2, 3, 6, 7, 8, 10, 11, 12]

这里的实现非常简单,注意两个 for 循环的次数即可,然后便是相邻数据比较,满足条件即交换数据。接下来我们要分析这种算法的复杂度。

4. 冒泡排序算法复杂度分析

对于算法的复杂度分析,会考虑以下几种情况:

时间复杂度:注意,这里的复杂度其实是包含 3 种情况,分别是最优复杂度、最坏情况复杂度和平均复杂度。由于我们不管怎么样,进行的 for 循环次数为:
$(n-1) + (n-2) + ... + 1 = O(n^2)$(n−1)+(n−2)+...+1=O(n2)
所以所有情况的复杂度都是$O(n^2)$O(n2)。但是对于最优的情况呢,有没有优化空间?要想在序列已有序的情况下使复杂度为 O (n),其实只需要增加一个标记量,如果内部循环没有发生任何的交换(swap),则表示序列已经有序,此时可以跳出循环。这杨我们对前面的代码进行简单的优化下:

def bubble_sort(nums):
 # 在这里添加一个交换的标记
 swapped = False
 for i in range(len(nums) - 1):
 for j in range(0, len(nums) - i - 1):
 if nums[j] > nums[j + 1]:
 nums[j], nums[j + 1] = nums[j + 1], nums[j]
 # 出现了元素交换则标记
 swapped = True
 # 如果一次循环都没有交换过数据,说明数据本身是有序的,则直接返回不用继续冒泡
 if not swapped:
 break

上面简单添加了一个交换的标记,如果一轮冒泡中不存在数据交换,说明数据本身有序,那么可以直接退出循环,不用继续冒泡排序。

空间复杂度:很明显这里我们没有用到额外的空间,冒泡排序的空间复杂度就是单纯的问题规模,也就是 $O(n)$O(n)。

5. 小结

本小节种我们详细介绍了排序算法种的最基本的算法:冒泡排序算法。接下来,我们给出了 Python 实现,并简单对代码进行了说明。最后分析了冒泡排序算法的时间和空间复杂度以及简单的优化点。

Tips:文中动图制作参考:https://visualgo.net/zh/sorting。