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

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

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

冒泡排序

以 Python 代码为例:

#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 百有序集合的 "排序"

 

选择排序

相对于冒泡排序,选择排序我认为是一种更好理解最直截了当的排序方式,下面用 Python 代码演示

看实际执行过程:

同样找来了一张图选择排序的意图非常明确,假如是从小到大的顺序排序,从左至右一个个位置上选择出剩余列表中最小的值

  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

类别: Algorithm. 标签: . 阅读(38). 订阅评论. TrackBack.
guest
2 Comments
Inline Feedbacks
View all comments
tumars
tumars
5 months ago

前两年看过这本书,最大的问题是算法在日常开发中很少用到,看完当下记住了,但很快就会忘记。

2
0
Would love your thoughts, please comment.x
()
x