引入📕
今天，我们来学习一种排序算法——冒泡排序。
首先，先问三个问题：
1.为什么要排序？🔥
想象一下，如果字典不是按照字母顺序排列，查找一个单词，你得查到什么时候？这就是为什么人们引入了分类的概念，因为其极大地帮助我们快速搜索物品。
或者说，排序是一种常用的整理信息的方法。排序可克服资料混乱、不便交流、查阅困难、挑选或取舍困难、不便安排等等问题。
2.有那些常用的排序算法？⌚
编辑
冒泡排序、选择排序、插入排序、归并排序等等都是常用的排序算法。
各种排序的复杂度、方式等方面都略有不同，下面这张图可以反映（图片参考自常用十大排序算法）：
编辑
3.什么是冒泡排序？🔨
冒泡排序（Bubble Sort），是一种 计算机科学领域的较简单的 排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的 元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中 二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
这是百度的说法，让我们来看看另一种说法。
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”。
来自《我的第一本算法书》。
总的来说，就是一句话：
通过不断比较相邻元素，将大的元素放到数组后面，最终完成排序。
这具体是什么原理呢？请看下面。
原理❓
文字解释📌
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
举个栗子（文字说明）👔
对6 3 2 5 4 1 这个乱序数字串进行冒泡排序。
第一步.3 2 5 4 1 6
第二步.2 3 4 1 5 6
第三步.2 3 1 4 5 6
第四步.2 1 3 4 5 6
第五步.1 2 3 4 5 6
这样就完成了。
举个栗子（图文混合说明）🌏
注：此处与上面的排序不太一样，上面是把大的优先放在后面，这是把小的依次放到前面。
编辑
在序列的最右边放置一个天平，比较天平两边的数字。如果右边的数字较小，就交换这两个数字的位置。
编辑
由于6＜7，所以交换这两个数字。
编辑
完成后，天平往左移动一个位置，比较两个数 字的大小。此处4＜6，所以无须交换。
编辑
继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。
编辑
不断对数字进行交换，天平最终到达了最左边。通过这一系列操作，序列中最小的数字就会移动到最左边。
编辑
最左边的数字已经归位
编辑
将天平移回最右边，然后重复之前的操作，直到天平到达左边第2个位置为止
编辑
当天平到达左边第2个位置时，序列中第2小的数字也就到达了指定位置。
编辑
将天平再次移回最右边，重复同样的操作直到所有数字都归位为止
编辑
排序中…
编辑
排序完成。
一些说明😱
时间复杂度
在冒泡排序中，第 1 轮需要比较 n -1 次，第 2 轮需要比较 n -2 次……第 n -1 轮需 要比较 1 次。因此，总的比较次数为 (n -1) +(n -2) +…+1 ≈ (n^2)/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。
不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输 入数据正好以从小到大的顺序排列，那么便不需要任何交换操作；反过来，输入数据要 是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时间复杂度为O(n^2 )。
两种不同的比较方法
相信大家都注意到了，文字说明与图文混合说明比较顺序是不同的。一个是把最大，第二大，第三大，...第n大依次放到后面；一个是把最小，第二小，...，第n小依次冒到前面。
不过，它们都是冒泡排序！
程序实现💐
注：此处用的是把最大，第二大，第三大，...第n大依次放到后面的冒泡顺序。
步骤图
编辑
代码😇
不用说了，很简单。（只插入中心部分）
for(int i=n;i>=1;i--) { for(int j=1;j<i;j++) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); } } }
优化👆
问题
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较。很显然，后面的比较没有意义的。
解决办法📐
设置bool变量flag（用于标记），如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。那么，就可以结束排序了。
最终代码🔭
bool b; for(int i=n;i>=1;i--) { b=false; for(int j=1;j<i;j++) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); b=true; } } if(b==false) break; }
结语
冒泡很简单，但是排序算法的基础。必须学会！
