7.3.1 交换排序之冒泡排序

所谓交换，就是根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

冒泡排序算法的基本思想是：假设待排序表长为n,从后往前（或从前往后）两两比较相邻元素的值。若为逆序（即A[i-1]>A[i])，则交换它们，直到序列比较完。我们称它为一趟冒泡。结果将最小的元素交换到待排序的第一个位置（关键字最小的元素如气泡一般逐渐往上漂浮，直到水面，这就是冒泡排序名字的由来）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置……，这样最多做n-1趟冒泡就把所有元素排好序。

void BubbleSort(ElemType A[],int n){
     //用冒泡排序法将序列A中的元素按从小到大排序
     for(i=0;i<n-1;i++){
         flag=false;//表示本趟冒泡是否发生交换的标志
         for(j=n-1;j>i;j--){//一趟冒泡过程
            if(A[j-1].key>A[j].key){//若为逆序
                swap（A[j-1],A[j]）;//交换
                flag=true;
            }
         }
         if(flag==false){
            return;//本趟遍历后没有发生交换，说明表已经有序
         }
     }  
}

空间效率：仅适用常数个辅助单元，因而空间复杂度为O(1)。

时间效率：当初始化序列有序时，显然这一趟冒泡后flag依然为false（本趟冒泡没有元素交换），从而直接跳出循环，比较次数为n-1，移动次数为0，从而最好情况下的时间复杂度为O(n);当初始化序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，而且每次比较都必须移动元素3次来交换元素位置。这种情况下比较次数为1+2+……+n-1=n(n-1)/2,移动次数=3n(n-1)/2。

从而，最坏情况下时间复杂度为O(n^2)。其平均时间复杂度也为O(n^2)。

稳定性：由于当i<j且A[i].key=A[j].key时，不会交换两个元素，从而冒泡排序是一个稳定的排序方法。

注意：冒泡排序中所产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说有序子序列中所有元素的关键字一定小于或者大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。