103. 冒泡排序

基本思想

第一趟在序列(A[0] ~ A[n-1])中从前往后进行相邻两个元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到A[n-1]中（即沉底），下一趟排序只需要在子序列（A[0]~A[n-2]）中进行；如果在某一趟排序中未交换元素，说明该序列已有序，则不再进行下一趟排序。

解题之法

template <class T>
void BubbleSort (T A[], int n){
    int i, j ,last;
    i = n - 1;
    while(i > 0){
        last = 0;
        for ( j = 0; j < i; j++){
          if(A[j+1] < A[j]){
            Swap(A[j], A[j + 1]);
            last = j;
}
}
    i = last;
}
}

复杂度

O(n*n) 稳定的