教材
源码
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 循环，控制的是整个排序过程；
网友评论