基本概念💦

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的思想就是每一轮把所有元素下标为01，12，23，34.....如此一直比较到n-1和n。若当前的比前一个小（这里我们默认为从小到大的排序），那么进行调换。每一轮下来一定有一个最大的元素“冒”到最后（顶端），也就是说在最坏的情况下，最多要进行n-1次。

例如有6个元素需要排序:

653412

第一趟排序:

比较65        得563412    

比较63        得536412     

比较64        得534612    

比较61        得534162     

比较62        得534126     

第一趟结束，最后的6固定下来

第二趟排序：

比较53        得354126

比较54        得345126

比较51        得341526

比较52        得341256

6已经固定所以56不比较

第二趟结束，5固定下来

第三趟排序：

比较34        得341256

比较41        得314256

比较42        得312456

5已经固定所以45不比较

第三趟结束，4固定下来。

第四趟排序：

比较31        得132456

比较32        得123456

4已经固定所以34不比较

第四趟结束，3固定下来

第五趟排序：

比较12        得123456

3已经固定所以23不比较

第五趟结束，2固定下来

1也随之固定下来

五趟结束后，6个整数就已经排序完成。排序过程中,大数慢慢地往后，相当于气泡上升，所以叫冒泡排序。

归纳上述排序过程,具体实现步骤如下:

①读人数据存放在a数组中。

②比较相邻的前后两个数据，如果前面数据大于后面的数据,就将两个数据交换。

③对数组的第0个数据到n-1个数据进行一次遍历后,最大的一个数据就“冒”到数组第n一1个位置。

④n=n一1,如果n不为0就重复前面二步,否则排序完成。

我们用动画看一下其过程：

程序实现

程序实现方法:用两层循环完成算法,外层循环i控制每轮要进行多少次的比较,第1轮比较n一1次,第2轮比较n-2....最后一轮比较1次。内层循环j控制每轮i次比较相邻两个元素是否逆序,若逆序就交换这两个元素。

具体程序如下：

在用冒泡排序的时候，我们发现，对于一些数据，并不一定要n-1次才可以排完。例如1 5 2 3 4 5，我们发现这种情况只需要一趟排序就可以将整个序列排完，若继续下去就大大增加了程序运行的时间而且浪费空间。于是，我们可以设置一个布尔类型的变量，判断是否有进行交换，如果没有，说明已经完成了排序，从而减少几趟排序。

那我们如何利用这个布尔变量呢。

举个栗子🌰

1 5 2 3 4 6 7

再此，我们要先确定好这个变量是用来干嘛的，这个变量是用来看还要不要执行。执行条件就是假，也就是还没有执行完呢，终止条件就是真，也就是执行完了呢。就以上面的例子而言，循环每次开始我们的布尔变量是true，所以该程序可以执行，第一趟我们对数列进行了调整，变量要变成假，代表还要继续，此时，数列已经有序化，下一次执行的时候并没有对数列进行调整，所以并没有将变量改为假，所以跳出循环，直接输出有序数列就行了。

具体程序如下：

部分格式和代码借鉴了《信息学奥赛一本通（C++）》

up打字不容易，思路整理更不容易，点一个免费的赞👍鼓励一下up吧！up是用手机打的字，眼睛👀都要瞎了，点个赞吧不浪费你们的时间，改天up给你们表演一个猴子上树！🐒