演算法从入门到「放弃」（6）- 冒泡排序
演算法从入门到「放弃」（6）- 冒泡排序
来自专栏 AnotherWorld
1 人赞了文章
本系列文章
演算法从入门到「放弃」（1）- 什么是演算法？
演算法从入门到「放弃」（2）- 分而治之和解决循环
排序系列
1. 演算法从入门到「放弃」（3）- 快速排序
2. 演算法从入门到「放弃」（4）- 插入排序
3. 演算法从入门到「放弃」（5）- 计数排序
本文提炼
冒泡排序演算法，一种通过交换数据元素位置来进行排序的交换排序演算法。
什么是冒泡排序？
定义来自于维基百科，冒泡排序，Bubble Sort.
冒泡排序，有时被称为「下沉排序」(sinking sort)，是一种简单的排序演算法，它反复地遍历列表进行排序，遍历过程中比较每一对相邻的项，如果它们的顺序是相反的，则交换它们。对列表的遍历是持续进行的，一直到列表变成有序，不需要交换为止。该演算法是一种比较排序，它以更小或更大的元素（根据实际情况而定）「冒泡」到列表顶部的方式命名。该演算法的优点是很简单，通俗易懂；但对于大多数问题来说，它太费时间且不切实际。如果输入列表中大部分元素都是有序的，只有一些很少的无序元素，那么气泡排序是可行的。
简而言之，我们假设要求是把输入数组中的元素按照从小到大排好序；那么从一个列表的头部开始，比较两个相邻的元素，如果第一个比第二大，则交换它们的位置，如果第二个比第一个大，就不用管它们；接著比较第二个和第三个，第三个和第四个...直到倒数第二个和倒数最后一个；第一遍结束的时候，我们至少可以保证最后一个元素是最大的。然后再继续重复这个过程（第二遍遍历的时候可以加上「保证倒数第二个元素是第二大的」，第三遍遍历的时候可以加上「保证倒数第三个元素是第三大的」......），直到列表中所有的元素都是有序，从小到大的。
基本思想
输入：一系列的无序元素（比如说，数字）组成的输入数组A
输出：冒泡排序的经过比较通俗易懂，就像我在什么是冒泡排序中介绍里说的一样，我们假设要求是把输入数组中的元素按照从小到大排好序；那么从一个列表的头部开始，比较两个相邻的元素，如果第一个比第二大，则交换它们的位置，如果第二个比第一个大，就不用管它们；接著比较第二个和第三个，第三个和第四个...直到倒数第二个和倒数最后一个；第一遍结束的时候，我们至少可以保证最后一个元素是最大的。然后再继续重复这个过程（第二遍遍历的时候可以加上「保证倒数第二个元素是第二大的」，第三遍遍历的时候可以加上「保证倒数第三个元素是第三大的」......），直到列表中所有的元素都是有序，从小到大的。
结果：输出数组B，里面包含的元素都是A 中的但是已经按照要求拍好了顺序（比如说，从小到大）
图解
评价演算法好坏
分类：排序演算法
目标数据结构：数组
最坏时间复杂度：比较部分O(n^2)，交换部分O(n^2)；总体O(n^2)
最优时间复杂度：比较部分O(n)，交换部分O(1)；总体O(n) 【这里解释一下，最好情况也就是原本的输入数组A 里面的元素就是符合条件排好序了，只需要遍历一遍就可以了】
平均时间复杂度：比较部分O(n^2)，交换部分O(n^2)；总体O(n^2)
最坏空间复杂度：O(1)
实例分析
假设现在有输入数组 A{6,5,3,1,8,7,2,4}
第一遍遍历，6和5对比，6比5大，所以交换位置；6和3对比，6比3大，再次交换位置；6和1比较，6比1大，交换位置；现在数组是{5,3,1,6,8,7,2,4}. 6和8对比，6比8小，不变；8和7对比，8比7大，交换位置；8和2对比，交换位置；8和4对比，交换位置；第一遍遍历结果是{5,3,1,6,7,2,4,8}. 我们找出了最大值是8.
第二遍遍历，过程和上述一样，我们找出了第二大的值是7.
第三遍遍历，过程和上述一样，我们找出了第三大的值是6.
......
第八遍遍历，过程和上述一样，我们找出了最小的值是1.
至此，我们得到了输出数组B{1,2,3,4,5,6,7,8}
流程展示图
代码展示
伪代码
伪代码来源：Bubble sort - Algorithmist
// 假设我们有一个array 名字是a，尺寸大小是nswapped = true //设定一个flag, 一开始是正确的 while swapped //开始交换循环 swapped = false for j from 0 to n - 1 //从0到n-1 if a[j] > a[j + 1] //如果前一个数大于后一个数 swap( a[j], a[j + 1] ) //交换两个数的位置 swapped = true
优化？
1. 每次遍历，都不需要考虑已经确定排序好的数。比如说，第一次遍历后，我们知道最后一个数已经确定了，那么最后一个数在下次遍历就不需要考虑了；第二次便利后，倒数第二个数和倒数第一个数就在第三次遍历中不需要被考虑了.....也就是说，第i 次遍历后，倒数第i 个数及其之后的数都不需要在i+1 次遍历中被考虑。
伪代码
// 假设我们有一个array 名字是a，尺寸大小是nfor i from 1 to n //还是会有n 遍遍历 swaps = 0 for j from 0 to n - i //常规交换步骤 if a[j] > a[j + 1] swap( a[j], a[j + 1] ) swaps = swaps + 1 if swaps = 0 //当swaps 是0，退出该遍历即可 break
2.
一个小小的改进就可以了。每次遍历，我们都去追踪数组中的元素是否交换了位置；如果没有，我们就可以放心大胆地认为序列里面的元素已经是有序排列好了的。
A small improvement can be made if each pass you keep track of whether or not an element was swapped. If not, you can safely assume the list is sorted.引自 Bubble sort - Algorithmist
伪代码
// 假设我们有一个array 名字是a，尺寸大小是nfor i from 2 to n //第一遍遍历我们追踪不了元素是否交换了位置，要从第二遍开始进行对比 swaps = 0 for j from 0 to n - 2 //只追踪到倒数第二大的数 if a[j] > a[j + 1] swap( a[j], a[j + 1] ) swaps = swaps + 1 if swaps = 0 break
在下一篇文章中，将著重讲的是选择排序演算法。
如果你觉得我的文章有用，顺手点个赞，关注下我的专栏或则留下你的评论吧！
推荐阅读：
