两种最基本的排序算法: 冒泡和选择

calendar Apr 14, 2020   ---   · 2 min read · 算法  ·
Share on: linkedin copy
因 COVID-19 漫延各自居家，也更有闲时，便拣起一本关于算法的书籍来研究。本不是科班出身，算法方面自然是自己的薄弱环节。平时用各种 SDK，只大概听说了些算法，仅能就自己如何选择哪种实现而作为参考。

如今阅读的是一本入门的书籍，名为 《算法图解》，英文版书名是 《Grokking Algorithms》。 该书图文并茂，十分适合初学者，关于排序最基本莫过于冒泡与选择排序。该书并未提及冒泡，而是直接从选择排序切入，在阅读本书之前我就一直对这两咱排序方式傻傻不分。一直以为头脑中的选择排序就是冒泡排序，那就来看下什么是真正的冒泡排序。

冒泡排序

以 Python 代码为例：
1items = [6, 5, 3, 1, 8, 7, 2, 4]
2length = len(items)
3
4for i in range(length):    #1
5    for j in range(length - i - 1):
6        if items[j] > items[j + 1]:
7            items[j], items[j + 1] = items[j + 1], items[j]  #2
8
9print(items)

#1: range(length) 和 range(0, length) 是一样的
#2: 这是 Python 交换两个值的写法，相当于用临时变量的方式 tmp = items[j]; items[j] = items[j + 1]; items[j + 1] = tmp

 网上找了一张非常直观的动态演示了整冒泡排序的过程 该图来自于 Sorting Algorithms - Bubble Sort

下面可以看到的更生动现实的排序执行过程



前面代码中的数字列表也是基于这个图来选择的。对冒泡排序大意的理解可以这样的

  1. 冒泡排序的每一步只作相邻两元素的交换
  2. 交换后的右端元素继续与下一个元素比较
  3. 大循环每次向左收缩一个元素
  4. 每次大循环都能把当前子列表中最大的元素冒泡到最右端

冒泡排序的时间复杂度是 O(n2)

冒泡排序效率最低效，存在过多的比较与交换，但它却有一个其他排序算法没有的好处，当某轮大循环(比如第一轮大循环) 中没有发生一次交换，那么说明排序已完成，可以立即返回。比如说对于有序集合，扫一遍就能完成 "排序"，效率就是 O(n)。看下面冒泡排序也能处理 100 百有序集合的 "排序"
 1def bubble_sort(items):
 2    exchanges = True
 3    for i in range(len(items)):
 4        if not exchanges:
 5            return
 6        exchanges = False
 7        for j in range(len(items) - i - 1):
 8            if items[j] > items[j + 1]:
 9                exchanges = True
10                items[j], items[j + 1] = items[j + 1], items[j]
11
12
13bubble_sort(list(range(1000000)))

选择排序

相对于冒泡排序，选择排序我认为是一种更好理解最直截了当的排序方式，下面用 Python 代码演示
1items = [6, 8, 3, 5, 9, 10, 7, 2, 4, 1]
2
3length = len(items)
4for i in range(length):
5    for j in range(i+1, length):
6        if items[i] > items[j]:
7            items[i], items[j] = items[j], items[i]
8
9print(items)

看实际执行过程：



同样找来了一张图 选择排序的意图非常明确，假如是从小到大的顺序排序，从左至右一个个位置上选择出剩余列表中最小的值
  1. 位置 1 处要放最小值，循环从右端子列表中选择谁比它还小，是的话交换值
  2. 然后同样的办法确定位置 2 处的值，子列表向右边收缩
  3. 每次大循环确定左边一个位置上的值

选择排序的时间复杂度也是是 O(n2)，但操作上比冒泡排序少一些，因为冒泡排序邻近元素相比较，交换次数要多，效率上选择排序比冒泡排序高那么一点点。

具体比较 10 万次对列表 [6, 8, 3, 6, 9, 10, 7, 2, 4, 1] 的排序，我测试选择和冒泡排序的平均时间分别为 1.58608 和 1.87929 秒，选择排序比冒泡快 15.6%。

链接：
  1. Algorithm Visualizer
  2. Sorting Algorithms
  3. VisuAlgo
永久链接 https://yanbin.blog/two-basic-sorting-algorithms/, 来自 隔叶黄莺 Yanbin's Blog
[版权声明] 本文采用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 进行许可。