局部有序和整体有序
在由一组整数组成的序列A[0, n-1]中，满足 $ A[i - 1] \leq A[i] $ 的相邻元素称为顺序的；否则是逆序的。
扫描交换
由有序序列的特征，我们可以通过不断改善局部的有序性实现整体的有序性：从前向后依次检查每一对相邻元素，一旦发现逆序即交换二者的位置。对于长度为n的序列，共需做n-1次比较，和不超过n-1次交换，这一过程称为一趟扫描交换。
起泡排序
void bubblesort(int A[], int n)
{
bool sorted = false; // 整体排序标志，先假定未排序
while(!sorted)
{
sorted = true; // 假定已排序
for(int i = 1; i < n; i++)
{
if(A[i-1] > A[i])
{
swap(A[i-1], A[i]); // 逆序交换
sorted = false; // 出现逆序，所以整体排序为false
}
}
n--; // 末元素已就位，可缩短待排序序列长度
}
} // 借助bool型标志位sorted，可及时提前退出，而不用总是蛮力地做n-1趟扫描交换
不可提前退出算法
void bubblesort(int A[], int n)
{
for(int i = 0; i < n-1; i++) // n-1趟扫描
{
for(int j = 0; j < n-1-i; j++) // 末元素已就位，可减少待排序个数
{
if(A[j] > A[j+1])
swap(A[j], A[j+1]);
}
}
}