动态可视化十大排序算法之冒泡排序

vlambda
2020-12-18

动态可视化十大排序算法之冒泡排序

提到排序算法呀，我想你肯定不陌生。这应该是学习编程时学到的第一个算法了吧。

我现在还能记得自己当时在 VC++ 6.0 上按照谭浩强老师的 C 语言教材敲出第一个冒泡排序时的激动心情。满满的成就感，不得不说，编程爱好者的快乐就是如此简单。

虽然排序在我们日常生活中很常见、常用。但是对于那时的自己来说还是很难理解的。而且自己也是在对比着书修改了很多遍才正确的编译运行。

当时我就想着要是有一个算法执行过程的动态图那就好了。我一直也在这样尝试着这样做，今天我就带你来体验下冒泡排序算法的动态执行过程。

话不多说，直接上干货，先带你看下效果，包你满意。

动态可视化十大排序算法之冒泡排序

不仅是简单的算法执行过程，我还会为你介绍一些改进的技巧，让你更加游刃有余，显示出自己的内功修养。

有必要手动写排序算法吗？

可能有人觉得现在不需要自己手动写排序算法了，用的时候直接调用编程语言内置的库函数就行了。

在日常的工作学习中，我觉得大部分人也就是这样做的，包括我自己在内。而且你自己写排序算法有 Bug 不说，就算没有 Bug，肯定也没有编程语言内置的库函数高效。

但是这并不能说我们不需要掌握排序算法了，我觉得主要原因有两个吧。

掌握排序算法可以帮助我们更好的理解计算机程序的执行过程，训练我们的编程逻辑。而且排序算法有很多变形，这些变形在特定的应用场景下会非常高效。
另外一个我觉得就是应对职场的面试了。数据结构和算法直接对应了你能不能通过笔试，进入面试。我之前做过一个互联网大厂的笔试，笔试就是 4 道编程题，时间一个半小时。我当时一道题都没 AC,心态直接爆炸，结果也就凉凉了。。。

冒泡排序

接下来，我们就来看一看冒泡排序算法，前面的动画不知道你看懂了吗？没看懂的话可以再看一遍。

动态可视化十大排序算法之冒泡排序

但是看懂就代表你可以写出完整的代码来吗？答案并不一定哦。

话不多说，先看下代码：

#!/usr/bin/python
# -*- coding:UTF-8 -*-
from typing import List

# Bubble Sort
def bubble_sort(array: List[int]) -> None:
  for i in range(len(array) - 1):
    flag = False
    # 如果前面的比后面的元素大，就交换
    for j in range(len(array) - 1 - i):
      if array[j] > array[j + 1]:
        array[j], array[j + 1] = array[j + 1], array[j]
        flag = True
    # 如果一轮完成，没有一个元素进行交换，则表明元素有序，退出循环
    if not flag:
      break

array = [3, 44, 38, 5, 47, 15]
print(array)
bubble_sort(array)
print(array)

冒泡排序的思想就是比较相邻之间的元素，如果 array[j] < array[j + 1],则就会互换相邻之间的元素。这样每轮迭代完后，总有一个元素可以到达此元素应该到达的位置。

每次到位的元素也就是第 K 大元素，举例说，第一次到位的是第一大元素，也就是最大值。第二次到位的是第二大元素，也就是次大值。

如何评价一个排序算法？

通过上面的程序，我们就实现了冒泡排序算法，那么如何评价一个排序算法呢？我想这个你在学习数据结构与算法的时候一定都学过。

主要有以下指标：

时间复杂度
空间复杂度
稳定性

这里我就不再一一叙述了，冒泡排序算法的时间复杂度是 O(n2)，空间复杂度是 O（1），是稳定的排序算法。

优化

时间复杂度是 O(n2) 的排序算法是比较耗时的，适用于小规模的数据，不适用于大规模的数据排序，那有没有优化的方法呢？

要想从时间复杂度的量级上优化，这个就只能换排序算法了。但是呢？有一些其他的技巧，可以减少算法的运行时间。是什么呢？

就是在第奇数次迭代的时候，从前往后比较，而偶数次迭代的时候，从后往前比较。这样虽然理论上还是 O(n2) 的时间复杂度，但是运行时间会降低不少。

#!/usr/bin/python
# -*- coding: UTF-8 -*-
import random
import time

# Bubble Sort
def bubble_sort(array):
  for i in range(len(array) - 1):
    flag = False
    for j in range(len(array) - 1 - i):
      if array[j] > array[j + 1]:
        array[j], array[j + 1] = array[j + 1], array[j]
        flag = True
    if not flag:
      break

def optim_bubble_sort(array):
  for i in range(len(array) - 1):
    flag = False
    if i % 2:
      for j in range(len(array) - 1 - (i // 2), (i // 2), -1):
        if array[j] < array[j - 1]:
          array[j], array[j - 1] = array[j - 1], array[j]
          flag = True
    else:
      for j in range((i // 2), len(array) - 1 - (i // 2)):
        if array[j] > array[j + 1]:
          array[j], array[j + 1] = array[j + 1], array[j]
          flag = True
    if not flag:
      break


if __name__ == "__main__":
        num = 10000

        array = [random.randint(0,num) for _ in range (num)]
        array_copy = array[:]
        #print(array)
        start = time.perf_counter()
        bubble_sort(array)

        end = time.perf_counter()
        #print(array)
        print(end - start)
        start = time.perf_counter()
        optim_bubble_sort(array_copy)
        end = time.perf_counter()
        #print(array_copy)
        print(end - start)

从运行结果上看，运行时间还是有提高的。这是 num 设置为 10000 的时候。提前给你打个预防针，如果你 num 设置的过大，比如 100000，很有可能排序需要等20分钟。。。

动态可视化十大排序算法之冒泡排序

总结

冒泡排序是一种时间复杂度较高的排序算法，所以呢大部分时候都是在教科书中出现，在实际的项目或者使用过程中很少有它的身影。

但是这种思想对于刚接触编程的人来说，还是比较容易理解的，如果上来就让你理解递归，理解快排，我觉得还是比较难的。有了前面的基础，在学习后面算法的过程中也会容易很多。

这个我觉得大多数人应该都能理解，但理解不代表掌握了。就像我在手写这些代码的时候还要调试一会呢，相信你也可以看到我代码字里行间的调试信息，所以建议你花点时间自己练习下。

下篇文章我们一起学习选择排序算法。

一个人可以走的更快，一群人可以走得更远

vlambda博客
学习文章列表