教材

https://www.jianshu.com/p/0cb335e22bba

源码

https://dsa.cs.tsinghua.edu.cn/~deng/ds/src_link/bubblesort/bubble1a.cpp.htm

0001 void bubblesort1A ( int A[], int n ) { //起泡排序算法（版本1A）：0 <= n
0002    bool sorted = false; //整体排序标志，首先假定尚未排序
0003    while ( !sorted ) { //在尚未确认已全局排序之前，逐趟进行扫描交换
0004       sorted = true; //假定已经排序
0005       for ( int i = 1; i < n; i++ ) { //自左向右逐对检查当前范围A[0, n)内的各相邻元素
0006          if ( A[i - 1] > A[i] ) { //一旦A[i - 1]与A[i]逆序，则
0007             swap ( A[i - 1], A[i] ); //交换之，并
0008             sorted = false; //因整体排序不能保证，需要清除排序标志
0009          }
0010       }
0011       n--; //至此末元素必然就位，故可以缩短待排序序列的有效长度
0012    }
0013 } //借助布尔型标志位sorted，可及时提前退出，而不致总是蛮力地做n - 1趟扫描交换

图解

图1.3

起泡排序完整过程演算

理解

• 优化：借助布尔型标志位sorted，可及时提前退出，而不致总是蛮力地做n-1趟扫描交换
• 小的数往前放，大的数往下放
• for 循环就是每一躺，每一躺索引变量 i 都是从下标 1 （代表数组的第2个元素）开始遍历，第一躺是i from [ 1 ] to [n-1]，第二躺是i from [ 1 ] to [n-2]，第三躺是i from [ 1 ] to [n-3]；
• 每走一趟当前躺里面最大的数字就会被放到当前躺的最后，每次安排好一个“本次最大的数”，即，随着躺次增加，每躺要遍历的数字个数也在稳定的减一；
• 如果把A[i]看做自己，那么A[i-1]就是自己前面的那个同志，自己和前面的人比，个子矮的就往前站；
• while 循环，控制的是整个排序过程；