局部有序和整体有序

在由一组整数组成的序列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]);        }    }}