冒泡排序

算法思路：
1、序列分為未排序部分和已排序部分，初始狀態(tài)為全部未排序
2、掃描未排序部分，調整相鄰元素的順序，使未排序部分最大元素沉底成為已排序部分的首元素
3、重復2直到有序

C++

template <typename T>
void bubbleSort(T arr[],int n){
    //在進行到n-1此掃描時，序列已經(jīng)有序
    for (int i = 0; i < n-1; i++) {
        //掃描未排序部分[0,n-1-i)，交換位序
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j]>arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
            }
        }
    }
}

關于邊界n-1-i
一趟掃描長度為n的序列，共需要n-1次比較，所以n-1，i個有序元素減少i次比較，所以n-1-i