说明：参考书目为《Computer Algorithms --- Introduction to Design and Analysis》（第三版）Sara Baase, Allen Van Gelder
部分内容参考自大工林晓惠老师的课程【算法设计与分析】讲解。林老师讲算法非常细致，让人很容易理解，推荐一波~
（如部分内容涉及侵权，请联系我删除，谢谢）
之前的文章请见：
【算法设计与分析】如何分析一个算法
【算法设计与分析】4.2 插入排序
本篇文章目录
冒泡排序
1. 定义
2. 排序过程示例
3. 算法代码
4. 复杂度分析
5. 正确性证明
6. 算法优化
依次比较相邻的两个元素，若逆序则交换两个元素。每趟冒泡排序都能将子序列的最大数据元素放在最终的位置上。若一趟冒泡排序没有做任何数据交换，则说明子序列已经升序，可提前终止排序。
输入：数组Element[] E，大小为n（n>=0）
输出：排序后的Element[] E
void bubbleSort(Element[] E, int n)
int numPairs; // 待比较的数据对数量。即排除已固定位置的数据，对剩下的子序列进行排序所需比较次数
boolean didSwitch; // 在一趟排序中是否有数据交换：true(有) false(没有)
int j;
numPairs = n - 1;
didSwitch = true;
while(didSwitch)
didSwitch = false;
for(j = 0; j < numPairs; j++)
if(E[j] > E[j+1])
E[j]与E[j+1]交换
didSwitch = true;
numPairs --;
return;习题4.2 (a)：最坏情况是完全逆序。
假设有n个数据元素完全逆序，第一趟冒泡排序需要比较n-1次，第二趟冒泡排序需要比较n-2次，...，最后一趟冒泡排序需要比较1次，将比较次数加起来就是
即，
习题4.2 (b)：最好情况是完全升序。只要做一趟比较，发现没有任何数据交换就停止排序，这样的比较次数只有第一趟的n-1次。
习题4.3 (a)：证明一趟冒泡排序后，数组的最后一个数据元素一定是最大的。
习题4.3 (b)：证明若一趟冒泡排序无交换，则整个数组已排好序。
习题4.4 (a)：证明如果某一趟排序中最后一次数据交换发生在 j 和 j+1 的位置，则数组从 j+1 到 n-1 的数据已处于最终排序后的位置上。
设某一趟排序时numpairs=k (j+1<k<=n-1)，最后一次数据交换发生在 j 和 j+1 的位置，则max(E[0], E[1],..., E[j])<E[j+1]<=...<=E[k-1]<=E[k]
又因为之前的循环numpairs=n-1,n-1,...,k+1, 则E[k]<=E[k+1]<=...<=E[n-2]<=E[n-1]
从而：max(E[0], E[1],..., E[j])<E[j+1]<=...<=E[n-2]<=E[n-1]，即数组中 j+1 到 n-1 的数据已处于最终排序后的位置上。
习题4.4 (b)：修改代码，如果某一趟排序中最后一次数据交换发生在 j 和 j+1 的位置，那么下一趟排序可以在 j+1 的位置提前结束。
void bubbleSort(Element[] E, int n)
int numPairs, lastSwitch;
boolean didSwitch;
int j;
numPairs = n - 1;
didSwitch = true;
while(didSwitch)
didSwitch = false;
for(j = 0; j < numPairs; j++)
if(E[j] > E[j+1])
E[j]与E[j+1]交换
didSwitch = true;
lastSwitch = j; // 记录最后一次数据交换的位置
numPairs = j; // 使下一趟排序可以在 j+1 的位置提前结束
return;习题4.4 (c)：这个改变会对算法的最坏情况有影响吗？
没有影响。因为算法的最坏情况是完全逆序，每一趟冒泡排序都需要不停地交换数据直到当前子序列的最后一个数据元素，即不存在某个子序列的尾部有升序的情况。
习题4.5：参考习题4.4的改进方案——优化子序列尾部的排序，能否对子序列的头部也进行算法优化？
习题4.4指的是如果最后一次数据交换发生在数组 j 和 j+1 的位置，那么下一趟排序可以在 j+1的位置提前结束；同理，如果首次数据交换发生在 j 和 j+1 的位置，那么下一趟排序应该从 j-1 的位置开始。
void bubbleSort(Element[] E, int n)
int numPairs, lastSwitch, firstSwitch;
boolean didSwitch, didFirstSwitch;
int j;
numPairs = n - 1;
firstSwitch = 0;
didSwitch = true;
while(didSwitch)
didSwitch = false;
didFirstSwitch = false;
for(j = firstSwitch; j < numPairs; j++) // 从上一趟排序初次进行数据交换的位置开始排序
if(E[j] > E[j+1])
E[j]与E[j+1]交换
didSwitch = true;
lastSwitch = j;
if(!didFirstSwitch)
if(j == 0)
firstSwitch = 0; // 如果第一个数据就发生交换，那么首次交换位置记为0
else
firstSwitch = j-1; // 记录该趟排序第一次数据交换的位置
didFirstSwitch = true;
numPairs = j;
return;