冒泡排序

简介

? 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

原理

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
5. 如果两个元素相等，是不会再交换的， 相同元素的前后顺序并没有改变，所以冒泡排序是一种==稳定排序==算法。{时间复杂度为o(n^2^)}

传统的冒泡排序过程

? 初始状态：3 6 4 2 11 10 5

第一趟排序：3 4 2 6 10 5 ==11== (11沉到未排序序列)

第二趟排序：3 2 4 6 5 ==10== 11 (10沉到未排序序列)

第三趟排序：2 3 4 5 ==6== 10 11 (6沉到未排序序列)

第四趟排序：2 3 4 ==5== 6 10 11 (5沉到未排序序列)

第五趟排序：2 3 ==4== 5 6 10 11 (4沉到未排序序列)

第六趟排序：2 ==3== 4 5 6 10 11 (3沉到未排序序列)

代码实现（传统）

#include <iostream>
using namespace std;

int main()
{        
    int a[7]={3,6,4,2,11,10,5}; 
    int i,j,t;
    for(i=0;i<7;i++)//外层循环：要比较的次数
    {
        for(j=0;j<6-i;j++)//内层循环：每次比较时，要比较的元素的范围；（这里就相当于j<n-i-1 ）
        {
            if(a[j]>a[j+1])//交换的三条语句
            {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
    for(i=0;i<7;i++)
    cout<<a[i]<<' ';
    return 0;
}

冒泡排序-优化

定义一个flag，用来判断有没有进行交换，如果在某次内层循环中没有交换操作，就说明此时数组已经是有序了的，不用再进行判断，这样可以节省时间。

代码实现（优化）

#include <iostream>
using namespace std;
int main()
{        
    int a[7]={3,6,4,2,11,10,5}; 
    int flag=1;
    int i,j,t;
    for(i=0;i<7 && flag;i++)//外层循环：要比较的次数
    {
        flag=0;
        for(j=0;j<6-i;j++)//内层循环：每次比较时，要比较的元素的范围；（这里就相当于j<n-i-1 ）
        {
            if(a[j]>a[j+1])//交换的三条语句
            {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                flag=1;
            }
        }
    }
    for(i=0;i<7;i++)
    cout<<a[i]<<' ';
    return 0;
}

冒泡排序

原文：https://www.cnblogs.com/little-ProMonkey/p/12273048.html