算法解析之冒泡排序

冒泡排序

算法思路：
1、序列分为未排序部分和已排序部分，初始状态为全部未排序
2、扫描未排序部分，调整相邻元素的顺序，使未排序部分最大元素沉底成为已排序部分的首元素
3、重复2直到有序

C++

template <typename T>
void bubbleSort(T arr[],int n){
    //在进行到n-1此扫描时，序列已经有序
    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