算法思想：
从数组中第一个数开始，依次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数的中的最大数并”冒泡”至数列的顶端。

算法步骤：
（1）从数组中第一个数开始，依次与下一个数比较并次交换比自己小的数，直到最后一个数。如果发生交换，则继续下面的步骤，如果未发生交换，则数组有序，排序结束，此时时间复杂度为O(n)；
（2）每一轮”冒泡”结束后，最大的数将出现在乱序数列的最后一位。重复步骤（1）。

稳定性：稳定排序。

时间复杂度： O(n)至O(n2)，平均时间复杂度为O(n2)。

最好的情况：如果待排序数据序列为正序，则一趟冒泡就可完成排序，排序码的比较次数为n-1次，且没有移动，时间复杂度为O(n)。

最坏的情况：如果待排序数据序列为逆序，则冒泡排序需要n-1次趟起泡，每趟进行n-i次排序码的比较和移动，即比较和移动次数均达到最大值：
比较次数:Cmax=∑i=1n−1(n−i)=n(n−1)/2=O(n2)
移动次数等于比较次数，因此最坏时间复杂度为O(n2)。

示例代码：
  void bubbleSort(int array[],int len){
    //循环的次数为数组长度减一，剩下的一个数不需要排序
    for(int i=0;i<len-1;++i){
        bool noswap=true;
        //循环次数为待排序数第一位数冒泡至最高位的比较次数
        for(int j=0;j<len-i-1;++j){
            if(array[j]>array[j+1]){
                array[j]=array[j]+array[j+1];
                array[j+1]=array[j]-array[j+1];
                array[j]=array[j]-array[j+1];
                //交换或者使用如下方式
                //a=a^b;
                //b=b^a;
                //a=a^b;
                noswap=false;
            }
        }
        if(noswap) break;
    }
}
冒泡排序是在相邻的两个记录进行比较和交换，每次交换只能上移或下移一个位置，导致总的比较与移动次数较多。
冒泡排序算法的改进:
     对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，
    则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。以下有两种改进算法：
     1．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,
        故在进行下一趟排序时只要扫描到pos位置即可。
        改进后算法如下:*/
    void Bubble_1(int r[], int n) {
        int i = n - 1;  //初始时,最后位置保持不变
        while (i > 0) {
            int pos = 0; //每趟开始时,无记录交换
            for (int j = 0; j < i; j++) {
                if (r[j] > r[j + 1]) {
                    pos = j; //记录交换的位置
                    int tmp = r[j];
                    r[j] = r[j + 1];
                    r[j + 1] = tmp;
                }
            }
            i = pos; //为下一趟排序作准备
        }
    }


2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法
    一次可以得到两个最终值(最大者和最小者) ,
        从而使排序趟数几乎减少了一半。
        改进后的算法实现为:*/
    void Bubble_2(int r[], int n) {
        int low = 0;
        int high = n - 1; //设置变量的初始值
        int tmp, j;
        while (low < high) {
            for (j = low; j < high; ++j) //正向冒泡,找到最大者
                if (r[j] > r[j + 1]) {
                    tmp = r[j];
                    r[j] = r[j + 1];
                    r[j + 1] = tmp;
                }
            --high;                    //修改high值, 前移一位
            for (j = high; j > low; --j) //反向冒泡,找到最小者
                if (r[j] < r[j - 1]) {
                    tmp = r[j];
                    r[j] = r[j - 1];
                    r[j - 1] = tmp;
                }
            ++low;                    //修改low值,后移一位
        }

    }
}

算法思想：
从数组中第一个数开始，依次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数的中的最大数并”冒泡”至数列的顶端。

算法步骤：
（1）从数组中第一个数开始，依次与下一个数比较并次交换比自己小的数，直到最后一个数。如果发生交换，则继续下面的步骤，如果未发生交换，则数组有序，排序结束，此时时间复杂度为O(n)；
（2）每一轮”冒泡”结束后，最大的数将出现在乱序数列的最后一位。重复步骤（1）。

稳定性：稳定排序。

时间复杂度： O(n)至O(n2)，平均时间复杂度为O(n2)。

最好的情况：如果待排序数据序列为正序，则一趟冒泡就可完成排序，排序码的比较次数为n-1次，且没有移动，时间复杂度为O(n)。

最坏的情况：如果待排序数据序列为逆序，则冒泡排序需要n-1次趟起泡，每趟进行n-i次排序码的比较和移动，即比较和移动次数均达到最大值：
比较次数:Cmax=∑i=1n−1(n−i)=n(n−1)/2=O(n2)
移动次数等于比较次数，因此最坏时间复杂度为O(n2)。

示例代码：
  void bubbleSort(int array[],int len){
    //循环的次数为数组长度减一，剩下的一个数不需要排序
    for(int i=0;i<len-1;++i){
        bool noswap=true;
        //循环次数为待排序数第一位数冒泡至最高位的比较次数
        for(int j=0;j<len-i-1;++j){
            if(array[j]>array[j+1]){
                array[j]=array[j]+array[j+1];
                array[j+1]=array[j]-array[j+1];
                array[j]=array[j]-array[j+1];
                //交换或者使用如下方式
                //a=a^b;
                //b=b^a;
                //a=a^b;
                noswap=false;
            }
        }
        if(noswap) break;
    }
}
冒泡排序是在相邻的两个记录进行比较和交换，每次交换只能上移或下移一个位置，导致总的比较与移动次数较多。
冒泡排序算法的改进:
     对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，
    则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。以下有两种改进算法：
     1．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,
        故在进行下一趟排序时只要扫描到pos位置即可。
        改进后算法如下:*/
    void Bubble_1(int r[], int n) {
        int i = n - 1;  //初始时,最后位置保持不变
        while (i > 0) {
            int pos = 0; //每趟开始时,无记录交换
            for (int j = 0; j < i; j++) {
                if (r[j] > r[j + 1]) {
                    pos = j; //记录交换的位置
                    int tmp = r[j];
                    r[j] = r[j + 1];
                    r[j + 1] = tmp;
                }
            }
            i = pos; //为下一趟排序作准备
        }
    }


2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法
    一次可以得到两个最终值(最大者和最小者) ,
        从而使排序趟数几乎减少了一半。
        改进后的算法实现为:*/
    void Bubble_2(int r[], int n) {
        int low = 0;
        int high = n - 1; //设置变量的初始值
        int tmp, j;
        while (low < high) {
            for (j = low; j < high; ++j) //正向冒泡,找到最大者
                if (r[j] > r[j + 1]) {
                    tmp = r[j];
                    r[j] = r[j + 1];
                    r[j + 1] = tmp;
                }
            --high;                    //修改high值, 前移一位
            for (j = high; j > low; --j) //反向冒泡,找到最小者
                if (r[j] < r[j - 1]) {
                    tmp = r[j];
                    r[j] = r[j - 1];
                    r[j - 1] = tmp;
                }
            ++low;                    //修改low值,后移一位
        }

    }
}